Planner Independent Plan Repair using Macro Actions

People

Supervisor

Research areas

Description

Plans are subject to fail, sooner or later something wrong will happen and replanning is the only possible solution to recover from the impasse. Altough equally complex in the worst case ([4]), plan repair via plan adaptation in contrast to replanning from scratch has proven to be effective for many practical situtations. Recently, plan repair has been tackled by exploting knowledge in form of macro actions ([2]), i.e. compressed sequence of actions encapsulating the sufficient and necessary conditions for executing those actions and their cumulative implications on the state of the system. The beauty of this formulation is that each macro can be encoded as additional knowledge and used by any planner together with standard atomic actions, preserving completeness but giving to the planner the capability of jumping from different states of the search space. Given a plan of actions, the problem is then to understand: which are the actually useful macro actions that can be extracted in such a way that the cost of using them does not overcome the actual benefits? Building on recent advances on the topic, the idea of this project is to answer to this question using deordering as a means to infer the causal structure of the plan in order to find set of actions which are as independent as possible among each other ([1], [3]). The project can be both theoretical and/or practical depending on the specific case.

Requirements

Artificial Intelligence course, principles of automated planning, some basic mathematical background, programming languages such as C++ and/or JAVA.

Background Literature

[1] Scala, Enrico Torasso, Pietro "Deordering and Numeric Macro Actions for Plan Repair" in Proc. of International Joint Conference on Artificial Intelligence (IJCAI 2015), Buenos Aires (Argentina) [2] Scala, Enrico. "Plan repair for resource constrained tasks via numeric macro actions." Twenty-Fourth International Conference on Automated Planning and Scheduling. 2014. [3] Siddiqui, Fazlul Hasan, and Patrik Haslum. "Plan quality optimisation via block decomposition." Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. AAAI Press, 2013. [4] Nebel, Bernhard, and Jana Koehler. "Plan reuse versus plan generation: A theoretical and empirical analysis." Artificial Intelligence 76.1 (1995): 427-454. [5] Fox, Maria, and Derek Long. "PDDL2. 1: An Extension to PDDL for Expressing Temporal Planning Domains." J. Artif. Intell. Res.(JAIR) 20 (2003): 61-124.

Updated:  8 September 2015/Responsible Officer:  Head of School/Page Contact:  CECS Marketing