Learning Situation-Dependent Costs:
Using Execution to Refine Planning Models

Karen Zita Haigh and Manuela M. Veloso,

School of Computer Science, Carnegie Mellon University

To appear in the Ninth International Workshop on the Principles of Diagnosis (DX98)

Physical environments are so complex that it is hard to hand-tune all of the domain knowledge, especially to model the dynamics of the environment. The work presented in this paper explores machine learning techniques to autonomously identify situations in the environment that affect plan quality. We introduce the concept of situation-dependent costs, where situational features can be attached to the costs used by the path planner. These costs effectively diagnose and predict situations the robot encounters so that the planner can generate paths that are appropriate for each situation.

We present an implementation of our situation-dependent learning approach in a real robotic system, ROGUE. ROGUE learns situation-dependent costs for arcs in a topological map of the environment; these costs are then used by the path planner to predict and avoid failures. In this article, we present the representation of the path planner and the navigation modules, and describe the execution trace. We show how training data is extracted from the execution trace. We present experimental results from a simulated, controlled environment as well as from data collected from the actual robot. Our approach effectively refines models of dynamic systems and improves the efficiency of generated plans.

  • Compressed Postscript (8 pages, 604K)