Expressive Optimal/Satisficing AI Planning, Execution and Repair

People

Supervisor

Research areas

Description

Planning is the problem of finding a course of actions whose execution leads the agent into a state satisfying a set of goals, while ensuring that such actions are actually feasible all along the entailed trajectory of states. In Artificial Intelligence the problem has been tackled from a knowledge representation point view; the purpose is to provide a declarative/model based framework for a form of reasoning which is independent from the specific domain of application but effective enough to obtain success in many application areas (http://sig-aps.org/).

In AI planning, such models are expressed using high level languages such as PDDL 3.0 [1]. Our interest is on the extension of this language that can expresses hybrid planning problems. Such problems require form of reasoning to deal with expressive and intertwined logical and numeric constraints, controllable (i.e., actions) and uncontrollable decisions (i.e., processes), complex global constraints. The challenge here is mostly computational: How can we build a system that is capable of generating plans for such problems in an effective way? Can we scale up?  Under which conditions?

Beside plan generation we are also interested in its optimization (regarding some notion of plan quality), execution (closing the loop with the sensing in the environment) and repair (what about plans that just need to be fixed?). We are investigating different solutions to the problem (subproblems) and because of that several projects can be started, such as:

 

  • Planning via Satisfiability Modulo Theory: This is a symbolic approach to planning where we ask a SMT solver to find a plan solution to our planning problem. The challenge here is on the particular SMT encoding to be adopted. For more information take a look at [13]

  • Planning via Heuristic Search: This is the eager/explicit approach to the problem. We are looking in particular at different heuristics via relaxation, to be plugged in standard search engine such as A*, Greedy Best First Search, Enforced Hill Climbing. For more information take a look at [14,15]

  • Deordering for Post/hoc Optimization and/or Robust Execution: In this approach we assume to have a plan, but we want to repair to improve quality. Have a look at [11,12]

  • Plan Repair using Macro Actions: Macro actions are a useful technique to compress sequence of actions in a macro operator, and have been used effectivly to solve complex computational problems (i.e., Rubik’s cube). In this context we look at the problem of understanding how macros can be used for the plan repair problem and how can they formulated to capture numeric structures as well. For more information look at [16]

  • From Numeric Planning to Conformant Probabilistic Planning: In this case we look at the problem of how numeric planning can be used to solve more complex problems such as Conformant Probabilistic Planning [17]

 

Projects can be theoretical, pratical and/or application oriented depending on the interests/background of the candidate. I am also open to discuss sponteneuous project in the AI planning field, or connected to it.

Requirements

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

Background Literature

1] 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.

[2] Barrett, Clark W., et al. "Satisfiability Modulo Theories." Handbook of satisfiability 185 (2009): 825-885.

[3] Hoffmann, Jörg. "The Metric-FF Planning System: Translating``Ignoring Delete Lists''to Numeric State Variables." Journal of Artificial Intelligence Research (2003): 291-341.

[4] Coles, Amanda Jane, et al. "COLIN: Planning with continuous linear numeric change." Journal of Artificial Intelligence Research (2012): 1-96.

[5] Rintanen, Jussi, Keijo Heljanko, and Ilkka Niemelä. "Planning as satisfiability: parallel plans and algorithms for plan search." Artificial Intelligence 170.12 (2006): 1031-1080.

[6] Rankooh, Masood Feyzbakhsh, and Gholamreza Ghassem-Sani. "New Encoding Methods for SAT-Based Temporal Planning." ICAPS. 2013.

[7] De Moura, Leonardo, and Nikolaj Bjørner. "Z3: An efficient SMT solver." Tools and Algorithms for the Construction and Analysis of Systems. Springer Berlin Heidelberg, 2008. 337-340.

[8] Bruttomesso, Roberto, et al. "The mathsat 4 smt solver." Computer Aided Verification. Springer Berlin Heidelberg, 2008.

[9] Scala, Enrico. "Numeric kernel for reasoning about plans involving numeric fluents." AI*IA 2013: Advances in Artificial Intelligence. Springer International Publishing, 2013. 263-275.

[10] Haslum, Patrik, and Héctor Geffner. "Admissible Heuristics for Optimal Planning." AIPS. 2000.

[11] 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)

[12] Backstrom, Christer. "Computational aspects of reordering plans." Journal of Artificial Intelligence Research (1998).

[13] Scala E., Ramirez M., Haslum P., Thiebaux S., "Numeric Planning with Disjunctive Global Constraints via SMT", ICAPS 2016

[14] Scala, E., Haslum, P. and Thiébaux, S., Heuristics for Numeric Planning via Subgoaling. ICAPS 2016

[15] Scala, E., Haslum, P., Thiébaux, S., Ramirez M., Interval-Based Relaxation for General Numeric Planning. ECAI 2016

[16] Scala, E. “Plan Repair for Resource Constrained Tasks via Numeric Macro Actions”, ICAPS 2014

[17] Brafman R., Taig R. “A Translation Based Approach to Probabilistic Conformant Planning”, ADT 2011

Keywords

AI Planning, Hybrid Planning, Replanning, Autononomous Systems, Numeric Planning, Repair, Autonomous Processes

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