Data processing: vehicles – navigation – and relative location – Vehicle control – guidance – operation – or indication – Automatic route guidance vehicle
Reexamination Certificate
1999-05-13
2002-09-17
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Vehicle control, guidance, operation, or indication
Automatic route guidance vehicle
C318S587000, C382S172000
Reexamination Certificate
active
06453223
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed generally to a method and apparatus for determining position and orientation of an object and, more particularly, to a method and apparatus for determining position and orientation of an object relative to a scene independent of infrastructure.
2. Description of the Background
High repeatability, position estimation is a key technology for mobile robotics applications such as seaport and manufacturing facility automation. Near term operations in those applications requires relatively precise positioning repeatabilities, such as, for example, approximately three millimeters. Three millimeters represents a significant improvement over the current industry standard of approximately five millimeters. The three millimeter repeatability must be achieved at an acceptable cost per unit. High end laser and inertial units are capable of meeting the technical specifications. However, their $20,000 to $100,000 plus per unit cost is far too high to be economically justifiable for most applications. Thus, a significant tradeoff exists between price and performance which prohibits flat floor mobile robotics companies from servicing existing demands in the market.
The least expensive positioning systems are so-called dead reckoning systems produced from low cost wheel encoders and a compass. Those systems produce an estimate of position based on the integration of rate measurements. Thus, they suffer from significant error accumulation in the estimate. High end dead reckoning systems, such as military grade inertial systems, reduce that problem by using rate sensors with very low error bias, but at a cost that is order of magnitudes higher than those acceptable to flat floor markets.
One low cost alternative is to combine the low cost dead reckoning system with a triangulation system, which can be used to reset the accumulated error by calculating a fix on the position. Triangulation systems do not perform integration, and thus are not affected by sensor bias. However, they suffer from dilution of precision problems that arise during the conversion of their measurements to the coordinate system of interest, e.g., a range and orientation of the sensor is converted to Cartesian space (xy). Triangulation systems take measurements with respect to external beacons or other items of infrastructure which make them vulnerable to sabotage. In certain industrial applications, sabotage is a key concern. Furthermore, the placement of beacons or other items of infrastructure represents a significant additional overhead cost to the end user. In certain applications, approximately one-third of the total cost of the system is due to the installation of beacons or other items of infrastructure.
Published German patent application DE 41 380 270 A discloses a method for the navigation of a self-propelled land vehicle in which markers are detected during travel, digitized and compared with stored data generated during a learning trip, in order to determine deviations from specified values whereby the deviations are processed into appropriate navigation control signals. The method is independent of artificial markers and ranges because natural landmarks are used as markers, which are captured as images by a video camera with two degrees of freedom. The actual position of the vehicle relative to a target point and the current vehicle direction in relation to the intended direction is calculated from the displacements of a pair of landmarks. Published European patent application EP 0 390 052 A discloses a landmark recognition system based on the perception, reasoning, action, and expectation (PREACTE) paradigm for the navigation of autonomous mobile robots. The system uses expectation to predict the appearance and disappearance of objects. The system also predicts the appearance of landmarks at different ranges and aspect angles, and uses map information to generate expectations of the scene. This system represents a classical solution, but suffers from problems associated with implementation and poor performance.
U.S. Pat. No. 4,847,769 entitled “Automated Vehicle Drift Correction” discloses a navigation system which carries out a dead reckoning calculation of the vehicles position based on inputs from sensors and the motion of a steering wheel in the preceding time interval. U.S. Pat. No. 5,307,278 entitled “Method Of Determining The Position Of A Vehicle, Arrangement For Determining The Position Of A Vehicle, As Well As A Vehicle Provided With Such An Arrangement”, also relies upon dead reckoning.
U.S. Pat. No. 5,170,352 entitled “Multi-Purpose Autonomous Vehicle With Path Plotting” is an example of an autonomous vehicle which operates in conjunction with a plurality of laser, sonic, and optical sensors. Such sensors detect targets and obstacles in the work area and provide coded signals which direct vehicles over a most expedient route to a target while avoiding any obstacles.
U.S. Pat. No. 5,363,305 entitled “Navigation System For A Mobile Robot” discloses an apparatus for creating and maintaining a map of an environment the mobile autonomous robot is to transverse. A credibility measure is increased or decreased whenever a map feature assigned to a location matches or does not match, respectively, a geometric beacon corresponding to such location.
U.S. Pat. No. 4,979,113 entitled “Automated Vehicle Control” discloses a system in which data identifying locations of notational points on the floor of the area of interest are entered into a computer together with a look-up table specifying pairs of those points between which movements of vehicles may be required.
U.S. Pat. No. 4,847,773 entitled “System For Navigating A Free-Ranging Vehicle” discloses a system in which the surface to be traversed carries a grid of passive marker elements with the vehicle being provided with detectors for detecting such elements.
U.S. Pat. No. 4,647,784 entitled “Vehicle Guidance and Control System” discloses a system in which vehicles determine their own position in relation to marker boards consisting of patterns of reflective coded strips by scanning a narrow laser beam in a predetermined direction across the strips. Positions can be determined by using triangulation.
U.S. Pat. No. 4,727,492 entitled “Vehicle Control And Guidance System” discloses a vehicle guidance system which uses dead reckoning to predict the position of the vehicle. At the end of predetermined intervals, the dead reckoning is corrected by an independent fixed-target detection system using a scanning laser.
Other low cost alternatives are based on the use of vision systems to take range readings, e.g., stereo vision, of known features in an environment, such as doorways and room corners. A position is determined based on such readings. Although that method does not require the placement of infrastructure, it suffers from the significant problem of shape dependence. Briefly, what a feature looks like depends upon the angle from which it is viewed. That problem entails such computational complexity that commercially practical vision systems that operate on natural features have never been produced.
Thus, while substantial work has been directed at solving the aforementioned problems, it is seen from the prior art discussed above that such problems have not been solved. Many position determining systems are still dependent upon infrastructure which is expensive. Furthermore, once the infrastructure is in place, the facility can usually not be modified without the additional expense of modifying the infrastructure. Additionally, robots relying upon such infrastructure can easily be sabotaged.
Dead reckoning systems do not provide the repeatability required by today's commercial application. Combining dead reckoning systems with some form of triangulation or other correction method introduces infrastructure, and all of the problems associated therewith.
Vision systems, which can provide higher accuracy than dead reckoning systems and which are typically free of artifici
Coulter Robert Craig
Kelly Alonzo James
Ollis Mark D.
Carnegie Mellon University
Cuchlinski Jr. William A.
Donnelly Arthur D.
Kirkpatrick & Lockhart LLP
LandOfFree
Infrastructure independent position determining system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Infrastructure independent position determining system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infrastructure independent position determining system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2819816