Solving Robot Navigation Problems with Initial Pose Uncertainty Using Real-Time Heuristic Search

Sven Koenig and Reid Simmons
Proceedings of the International Conference on Artificial Intelligence Planning Systems, 1998, pp. 144 - 153.


Download
  • Adobe portable document format (pdf) (100KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
We study goal-directed navigation tasks in mazes, where the robots know the maze but do not know their initial pose (position and orientation). These search tasks can be modeled as planning tasks in large non-deterministic domains whose states are sets of poses. They can be solved efficiently by interleaving planning and plan execution, which can reduce the sum of planning and plan-execution time because it allows the robots to gather information early. We show how Min-Max LRTA*, a real-time heuristic search method, can solve these and other planning tasks in non-deterministic domains efficiently. It allows for fine-grained control over how much planning to do between plan executions, uses heuristic knowledge to guide planning, and improves its plan-execution time as it solves similar planning tasks, until its plan-execution time is at least worst-case optimal. We also show that Min-Max LRTA* solves the goal-directed navigation tasks fast, converges quickly, and requires only a small amount of memory.

Notes
Associated Lab(s) / Group(s): Reliable Autonomous Systems Lab
Associated Project(s): Xavier

Text Reference
Sven Koenig and Reid Simmons, "Solving Robot Navigation Problems with Initial Pose Uncertainty Using Real-Time Heuristic Search," Proceedings of the International Conference on Artificial Intelligence Planning Systems, 1998, pp. 144 - 153.

BibTeX Reference
@inproceedings{Koenig_1998_3859,
   author = "Sven Koenig and Reid Simmons",
   title = "Solving Robot Navigation Problems with Initial Pose Uncertainty Using Real-Time Heuristic Search",
   booktitle = "Proceedings of the International Conference on Artificial Intelligence Planning Systems",
   pages = "144 - 153",
   year = "1998",
}