In recent years, autonomous robots, including Xavier, Martha [ 1], Rhino [ 2,3], Minerva,and Remote Agent, have shown impressive performance in long-term demonstrations. In NASA’s Deep Space program, for example, an - tonomous spacecraft controller, called the Remote Agent [ 5], has autonomously performed a scienti c experiment in space. At Carnegie Mellon University, Xavier [ 6], another autonomous mobile robot, navigated through an o ce - vironment for more than a year, allowing people to issue navigation commands and monitor their execution via the Internet. In 1998, Minerva [ 7] acted for 13 days as a museum tourguide in the Smithsonian Museum, and led several thousand people through an exhibition. These autonomous robots have in common that they rely on plan-based c- trol in order to achieve better problem-solving competence. In the plan-based approach, robots generate control actions by maintaining and executing a plan that is e ective and has a high expected utility with respect to the robots’ c- rent goals and beliefs. Plans are robot control programs that a robot can not only execute but also reason about and manipulate [ 4]. Thus, a plan-based c- troller is able to manage and adapt the robot’s intended course of action — the plan — while executing it and can thereby better achieve complex and changing tasks.
