Accession Number:

ADA326022

Title:

Landmark-Based Robot Navigation,

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Lazanas, Anthony
• Latombe, Jean-Claude

Report Date:

1992-05-01

Pagination or Media Count:

57.0

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 andor its workspace to be specifically engineered. This leads us to view robotworkspace 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
• Bionics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE