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.