Exploiting Relevance to Improve Robustness and Flexibility in Plan Generation and Execution

Automated plan generation and execution is an essential component of most autonomous agents. An agent's model of the world is often incomplete or incorrect, and its environment is typically noisy. To account for potential discrepancies between the agent's model of the world and the true state of the world, the planning techniques and representations used should enable flexible and robust agent behaviour. The agent should react swiftly when unexpected changes occur to assess the impact of the discrepancy and to accommodate as necessary. In particular, the agent should avoid unnecessary replanning and recognize changes that are irrelevant for its plan to achieve the goal.In this dissertation we address various aspects of the planning process including (1) how to synthesize a plan, (2) what a plan should constitute and how we should represent one, and (3) how to effectively execute a plan. We enable robust and flexible agent behaviour by exploiting the notion of relevance in each of the key planning areas. Intuitively, relevance characterizes what is important to consider as a sufficient condition for some property to hold. We apply relevance to the key areas of automated planning to achieve the following contributions: (1) increased flexibility of partial-order plans, (2) improved robustness of partial-order plan execution, (3) robust execution of temporally constrained plans, and (4) improved efficiency of plan generation with non-deterministic action effects.To increase the flexibility of partial-order plans, we introduce an effective method for generating optimally relaxed partial-order plans. For the execution of a partial-order plan, we leverage regression to generalize an input plan, resulting in an execution monitoring framework that is far more robust than previous approaches. We incorporate the expressive power of temporal constraints and provide a means for monitoring the execution of a temporally constrained plan, building on our approach for executing a partial-order plan. Finally, we introduce a suite of techniques that leverage relevance to produce a state-of-the-art planner for domains with non-deterministic action effects. For each of these four areas, we investigate the theoretical properties surrounding our methods and empirically demonstrate their feasibility in comparison to the previous state of the art.Ph.D