Accession Number : ADA326022
Title : Landmark-Based Robot Navigation,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Lazanas, Anthony ; Latombe, Jean-Claude
PDF Url : ADA326022
Report Date : MAY 1992
Pagination or Media Count : 57
Abstract : Achieving goals despite uncertainty in control and sensing may require robots to perform complicated motion planning and execution monitoring. This paper describes a reduced version of the general planning problem in the presence of uncertainty and a complete polynomial algorithm solving it. The planner computes a guaranteed plan (for given uncertainty bounds) by backchaining non-directional preimages of the goal until one fully contains the set of possible initial positions of the robot. The planner assumes that landmarks are scattered across the workspace, that robot control and sensing are perfect within the fields of influence of these landmarks, and that control is imperfect and sensing null outside these fields. The polynomiality and completeness of the algorithm derive from these simplifying assumptions, whose satisfaction may require the robot and/or its workspace to be specifically engineered. This leads us to view robot/workspace engineering as a means to make planning problems tractable. A computer program embedding the planner was implemented, along with navigation techniques and a robot simulator. Several examples run with this program are presented in this paper. Non-implemented extensions of the planner are also discussed.
Descriptors : *ROBOTS, *DIRECTION FINDING, *WORKPLACE LAYOUT, COMPUTER PROGRAMS, ALGORITHMS, ROBOTICS, ADAPTIVE CONTROL SYSTEMS, NAVIGATION COMPUTERS, PATTERN RECOGNITION, ARTIFICIAL INTELLIGENCE, COLLISION AVOIDANCE, NAVIGATION REFERENCE, REACTION CONTROL SYSTEMS.
Subject Categories : Cybernetics
Distribution Statement : APPROVED FOR PUBLIC RELEASE