Robot Navigation with Markov Models: A Framework for Path Planning and Learning with Limited Computational Resources

Sven Koenig, Richard Goodwin, and Reid Simmons
Proceedings of the International Workshop on Reasoning with Uncertainty in Robotics, December, 1995.


Download
  • Adobe portable document format (pdf) (76KB)
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
Navigation methods for mobile robots need to take various sources of uncertainty into account in order to get robust performance. The ability to improve performance with experience and to adapt to new circumstances is equally important for long-term operation. Real-time constraints, limited computation and memory, as well as the cost of collecting training data also need to be accounted for. In this paper, we discuss our evolving architecture for mobile robot navigation that we use as a test-bed for evaluating methods for dealing with uncertainty in the face of real-time constraints and limited computational resources.

Our architecture is based on POMDP models that explicitly represent actuator uncertainty, sensor uncertainty, and approximate knowledge of the environment (such as uncertain metric information). Using this model, the robot is able to track its likely location as it navigates through a building. In this paper, we discuss additions to the architecture: a learning component that allows the robot to improve the POMDP model from experience, and a decision-theoretic path planner that takes into account the expected performance of the robot as well as probabilistic information about the state of the world. A key aspect of both additions is the efficient allocation of computational resources.


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

Text Reference
Sven Koenig, Richard Goodwin, and Reid Simmons, "Robot Navigation with Markov Models: A Framework for Path Planning and Learning with Limited Computational Resources," Proceedings of the International Workshop on Reasoning with Uncertainty in Robotics, December, 1995.

BibTeX Reference
@inproceedings{Simmons_1995_3149,
   author = "Sven Koenig and Richard Goodwin and Reid Simmons",
   title = "Robot Navigation with Markov Models: A Framework for Path Planning and Learning with Limited Computational Resources",
   booktitle = "Proceedings of the International Workshop on Reasoning with Uncertainty in Robotics",
   month = "December",
   year = "1995",
}