Exploiting Relevance to Improve Robustness and Flexibility in Plan Generation and Execution
Automated Planning is the subfield of Artificial Intelligence that investigates principles and methods for generating and executing a prescribed set of ordered actions -- a plan -- to realize a specified objective. These tasks must often be performed in the face of inaccurate information about the state of the world, and with inaccurate models of the effects actions. The description of the state of the world can be enormous. As such, successful plan generation and execution systems must understand what details are relevant to the task at hand. The status of a traffic light, for example, is relevant to a mobile agent when crossing a busy street, but not when using the sidewalk.
We leverage various notions of relevance to improve the robustness, flexibility, and efficiency of different plan generation and execution techniques. The contributions address four key areas: (1) improving the flexibility of existing plans by removing irrelevant ordering constraints between actions; (2) generalizing flexible plans to produce robust executions in the face of unexpected changes to the environment; (3) characterizing what is relevant from a history of executed actions in order to maintain satisfaction of a set of temporal constraints during execution; and (4) applying relevance-based techniques in a variety of ways to improve plan generation in an environment with uncertain action outcomes. Every contribution uses a form of relevance, in some way, to improve upon the previous state of the art.
We demonstrate how relevance can improve the robustness of a plan by orders of magnitude, and how exploiting such robust plans can avoid costly re-planning in exponentially fewer states of the world. We also show how focusing on a temporally relevant subset of an execution history substantially reduces the cognitive burden for an execution system when timing constraints must be enforced during plan execution (e.g., the cookies must cool for at least 3 minutes before serving). Finally, we present a suite of relevance-based techniques for the generation of plans with uncertain action outcomes. The resulting system is orders of magnitude better than the previous state of the art, using multiple metrics.
