ActuPlan is a automated planner designed to solve planning problems having concurrent actions and uncertainty on time (duration of actions). ActuPlan has two variants. Both variants generate plans under a given threshold (parameter) on their probability of success. ActuPlan^NC generates optimal non-conditional (conformant) plans. A non-conditional plan is a set of partially ordered labelled actions. ActuPlan^C generates conditional plans which are near optimal under some reasonable restrictions. The conditional plans are expressed using a form of finite state machines where transitions are constrained by time intervals.

The ActuPlan project has been initiated during the Ph.D. of Éric Beaudry at Université de Sherbrooke which has been supervised by Professors Froduald Kabanza (director of the Planiart lab) and François Michaud (director of IntRoLab and Canada Research Chairholder in Mobile Robotics and Intelligent Autonomous Systems). The project is now maintained at GDAC lab at Université du Québec à Montréal.

Contact information: eric <dot> beaudry <at> gmail <dot> com

Features

Temporal planning with concurrent actions.
Time constraints on goals (deadlines).
Various continuous probabilistic distributions (ex: constant, uniform, normal, exponential) to model duration and the cost of actions.
Temporal heuristics: H_max (admissible).
Optimization criterion: (expected) makespan, actions' costs or linear combination.
Partial satisfaction of goals (each objective can have an abortion cost) [Experimental].
Approximate Bayesian Network estimation algorithm (direct sampling).

Download

Binary Package: ActuPlan-1.0.jar (330 KiB)
Sample planning domains and problems: ActuPlan-examples.zip (16 KiB)

Warnings and Disclaims:

ActuPlan is an experimental automated planner and comes with absolutely no guaranty. Use it at your own risks. Université de Sherbrooke and Université du Québec à Montréal cannot be responsible of any damage or lost following the use of ActuPlan.
You can use ActuPlan freely for research and educational purpose.
Commercial usage is not allowed. Commercial users must obtain a licence before using it.

Instructions

ActuPlan can be invoked through a command line interface. Since ActuPlan is written in Java programming language, it requires a Java VM. OpenJDK VM is recommended.

Command line syntax

The non-conditional planner (ActuPlan^NC) is invoked by the following command:

java -cp ActuPlan-1.0.jar actuplan.ActuPlanNC [options] domain.apl problem1.apl [problem2.apl ... problemN.apl]

The conditional planner (ActuPlan^C) is invoked by the following command:

java -cp ActuPlan-1.0.jar actuplan.ActuPlanC [options] domain.apl problem1.apl [problem2.apl ... problemN.apl]

Parameters are :

domain.apl is the specification of the domain.
problem1.apl ... problemN.apl are the specification of problems.
[options] ares:

-alpha [0.0-1.0] specifies the threshold on the probability of success of generated plans (default: 0.9).
-beta [0.0-1.0] specifies the threshold on the probability of success of pre-generated non-conditional plans to build the conditional plan (default: 0.5).
-maxPlanningTime seconds specifies the maximum allowed time for planning.
-nbSamples nbsamples specifies the number of samples in the Bayean network.
-outplan specifies that plans should be outputted in files (problemX.plan or problemX.cplan).
-d [0-5] specifies the debugging level.
-hw heuristicWeight specifies the weight of the heuristic (default: 1.0).

Example

java -cp ActuPlan-1.0.jar domain-file transport.apl transport_2t_2g.apl

Java VM tuning

ActuPlan may require a huge amount of memory. Default parameters of the Java Virtual Machine may be not appropriate for solving large problems. More memory can be allocated to the VM by setting a greater limit of the heap size using the "-Xmx" parameter. Please refer to your Java VM's documentation for additional information. The garbage collector tends to be less efficient when the actual required memory is close to the maximum heap's size. If you get an OutOfMemoryError, then you need to increase the maximum heap size. The performance of ActuPlan can be also improved using the server VM using the "-server" parameter. To check if you put a correct size of the VM's heap, add the -Xprof parameter to report the memory usage at the end of VM's process. If GC time takes more than 10% of the total run time, consider increasing the maximum heap size. It is strongly not recommended to set a heap size larger than the size of physical memory.

Example:

java -Xprof -server -Xmx2048m -cp ActuPlan-1.0.jar domain-file transport.apl transport_2t_2g.apl

Sample Domains

Few samples specifications are provided the following domains:

Transport (see SimTransport to animate generated plans)
Rovers
Satellites
NASA EVA

Transport Domain

Domain specification

domain
            {

               types { Location, Object, Truck }

               world {

                  predicate
            Link(Location,Location);

                  numeric  
            Distance(Location,Location);

               }

               state {

                  function  Location
            PosRobot(Truck);

                  function  Location
            PosObject(Object);

                  function 
            Truck    OnWhichTruck(Object);

               }

            /************************************

            A c t i o n s 

            *************************************/

               action Drive(Truck t, Location orig, Location
            dest){

                   duration:

            normal 1.2 * Distance(orig, dest) Distance(orig, dest)*0.1;

                   conditions:

                      @start: orig !=
            dest;

            @start: PosRobot(t) = orig;

            @start: Link(orig, dest);

                   effects:

                      @end:
            PosRobot(t) = dest;

               }

               action Load(Truck t, Location l, Object o){

                  duration:

                     uniform 30
            60;

                  conditions:

                     @overall:
            PosRobot(t) = l;

                     @start:
            PosObject(o) = l;

                     @start:
            OnWhichTruck(o) = undefined;

                  effects:

                     @end:
            PosObject(o) = undefined;

                     @end:
            OnWhichTruck(o) = t;

               }

               action Unload(Truck t, Location l, Object o){

                  duration:

                     uniform 30
            60;

                  conditions:

                    @overall:
            PosRobot(t) = l;

                    @start:
            OnWhichTruck(o) = t;

                    @start:
            PosObject(o) = undefined;

                  effects:

                    @end:
            PosObject(o) = l;

                    @end:
            OnWhichTruck(o) = undefined;

                }

            }

Problem

            {

              Objects {

                Location l0, l1, l2, l3, l4, l5, l6, l7,
            l8, l9;

                Object b0, b1;

                Truck r0;

              }

              WorldState {

            Link(l0,l1);      
            Link(l1,l0);

            Link(l0,l4);      
            Link(l4,l0);

                  [...]

                 Distance(l0,l0)=0.0;

                 Distance(l0,l1)=237.5137835588944;

                 Distance(l0,l2)=478.54588497403375;

                 Distance(l0,l3)=509.89036111283906;

                 Distance(l0,l4)=279.1982989828561;

                 Distance(l0,l5)=485.38268248461407;

                  [...]

              }

              InitialState{

                 PosRobot(r0)=l2;

                 PosObject(b0)=l9;

                 OnWhichTruck(b0) = undefined;

                 PosObject(b1)=l4;

                 OnWhichTruck(b1) = undefined;

              }

              Goal{

                 PosObject(b0)=l6[1820.0];

                 PosObject(b1)=l8[4000.0];

              }

            }

Non-Conditional Plan

Plan {
a0: Drive(r0,l2,l1);
a1: Drive(r0,l1,l4);
a2: Load(r0,l4,b1);
a3: Drive(r0,l4,l9);
a4: Load(r0,l9,b0);
a5: Drive(r0,l9,l6);
a6: Unload(r0,l6,b0);
a7: Drive(r0,l6,l8);
a8: Unload(r0,l8,b1);
a0 < a1;
a1 < a2;
a1 < a3;
a2 < a3;
a2 < a8;
a3 < a4;
a3 < a5;
a4 < a5;
a4 < a6;
a5 < a6;
a5 < a7;
a6 < a7;
a7 < a8;
}

The < symbol is used to express a partial order between to labelled action.

Conditional Plan

ConditionalPlan {
s0{
Drive(r0,l2,l1) [0;∞] {} -> s1 t1;
}
s1{
Drive(r0,l1,l4) [0;∞] {t1 } -> s2 t10;
}
s2{
Load(r0,l4,b1) [0;∞] {t10 } -> s3 t38;
}
s3{
Drive(r0,l4,l8) [0;635.3] {t10 t38 } -> s4 54;
Drive(r0,l4,l9) [635.3;∞] {t10 t38 } -> s5 t55;
}
s4{
Unload(r0,l8,b1) [0;∞] {t38 t54 } -> s6 t114;
}
s6{
Drive(r0,l8,l9) [0;∞] {t54 t114 } -> s7 t122;
}
s5{
Load(r0,l9,b0) [0;∞] {t55 } -> s8 t58;
}
s8{
Drive(r0,l9,l6) [0;∞] {t55 t58 } -> s9 t67;
}
s9{
Unload(r0,l6,b0) [0;∞] {t58 t67 } -> s10 t310;
}
s10{
Drive(r0,l6,l8) [0;∞] {t67 t310 } -> s11 t323;
}
s11{
Unload(r0,l8,b1) [0;∞] {t38 t323 } -> s12 t425;
}
s12{
}
s7{
Load(r0,l9,b0) [0;∞] {t122 } -> s13 t130;
}
s13{
Drive(r0,l9,l6) [0;∞] {t122 t130 } -> s14 t138;
}
s14{
Unload(r0,l6,b0) [0;∞] {t130 t138 } -> s15 t428;
}
s15{
}
}

The times in interval [min,max] specifies the minimum and maximum time an action can be started.

Specification Language for Domains and Problems

ActuPlan has its own specification language for domains and problems. Even this language shares some fundamental properties with PDDL (Planning Domain Definition Language), it has several differences. The ActuPlan's specification language supports predicates and discrete and numerical state-variables. The implementation of a fully compatible PDDL parser is also considered.

In ActuPlan, the world state is divided in static and dynamic parts which are respectively defined in "world" and "state" sections. By default, actions have 1 time unit of duration and cost 0 unit. The default objective function is defined as the sum of the cost of actions + the makesplan of the plan. ActuPlan optimizes the expected value of this total cost.

Domain - EBNF Grammar

Here is the simplified EBNF grammar used for domain specification. Few simplifications were made to make it more readable. For instance, predicates, functions and numerics may have zero parameters. Conditions @end are also forbidden due to limitations.

<DOMAIN> ::= "domain" "{" <TYPES> <WORLDDEF> <STATEDEF> <ACTIONDEF>* "}"

<TYPES> ::= "types" "{"<TYPE> ( "," <TYPE> )* "}"

<WORLDDEF> ::= "world" "{" ( <PREDICATEDEF> | <FUNCTIONDEF> | <NUMERICDEF>)* "}"

<PREDICATEDEF> ::= "predicate" <PREDICATE> "("<TYPE> ( "," <TYPE> )* ")" ";"

<FUNCTIONDEF> ::= <TYPE> "function" <FUNCTION> "(" <TYPE> ( "," <TYPE> )* ")" ";"

<NUMERICDEF> ::= "numeric" <NUMERIC> "("<TYPE> ( "," <TYPE> )* ")" ";"

<ACTIONDEF> ::= "action" <ACTION> "(" <TYPE> <VAR> ("," <TYPE> <VAR> ")" "{" <ACTIONDUR>? <COST>? <CONDITIONSDEF> <EFFECTSDEF> "}"

<ACTIONDUR> ::= "duration" ":" <DISTRIBUTION> ";"

<COST> ::= "cost" ":" <DISTRIBUTION> ";"

<DISTRIBUTION> :::= "constant" <EXP>
            |   "uniform" <EXP:min> <EXP:max>
            |   "normal" <EXP:mu> <EXP:sigma>
            |   "exponential" <EXP:mean>

<CONDITIONSDEF> ::= "conditions" ":" <CONDITIONS>*

<CONDITIONS> ::= <WHEN> (<PRED_COND> | <FUNC_COND> | <NUM_COND> | <VARSDIFF>) ";"

<PRED_COND> ::= <PREDICATE> "!"? "(" <VAR> ( "," <VAR> )* ")"

<FUNC_COND> ::= <FUNCTION> "!"? "(" <VAR> ( "," <VAR> )* ")" "=" (<VAR> | "undefined")

<NUM_COND> ::= <NUMERIC> "(" <VAR> ( "," <VAR> )* ")" ("<" | "<=" | "=" | ">=" | ">")

<VARSDIFF> ::=    <VAR> "!=" <VAR>

<EFFECTSDEF> ::= "conditions" ":" <EFFECTS>*

<EFFECT> ::= <WHEN> (<FUNC_ASSIGN> | <PRED_EFF> | <NUMERIC_EFF> )";"

<FUNC_ASSIGN> ::= <FUNCTION> "(" <VAR> ( "," <VAR> )* ")" "=" (<VAR> | "undefined")

<PRED_EFF> ::= <PREDICATE> "!"? "(" <VAR> ( "," <VAR> )* ")"

<NUMERIC_EFF> ::= <NUMERIC> "("<VAR> ( "," <VAR> )* ")" = <EXP>
            |    ("increase" | "decrease") <NUMERIC> "("<VAR> ( "," <VAR> )* ")" <EXP>

<EXP> ::= <NUMERIC> "("<VAR> ( "," <VAR> )* ")"
            |    <NUMBER>
            |    <EXP> * <EXP>
            |    <EXP> / <EXP>
            |    <EXP> + <EXP>
            |    <EXP> - <EXP>
            |    "(" <EXP> ")"

<TYPE> ::= <ID>

<PREDICATE> ::= <ID>

<FUNCTION> ::= <ID>

<NUMERIC> ::= <ID>

<VAR> ::= <ID>

<ID> = [a-zA-Z][a-zA-Z0-9_]*

<NUMBER> = [0-9]+(.[0-9]+)?

Problem - EBNF Grammar

<PROBLEM> ::= "Problem" "{" <OBJECTS> <WORLDSTATE> <INITIALSTATE> <GOAL> "}"

<OBJECTS> ::= "Object" "{" (<TYPE> <OBJECT>+ ";")* "}"

<WORLDSTATE> ::= "WorldState" "{" (<PREDICATE2> | <FUNCTION2> | <NUMERIC2>)* "}"

<INITIALSTATE> ::= "InitialState" "{" (<PREDICATE2> | <FUNCTION2> | <NUMERIC2>)* "}"

<PREDICATE2> ::= <PREDICATE> "(" <OBJECT> ("," <OBJECT>)* ")" ";"

<FUNCTION2> ::= <FUNCTION> "(" <OBJECT> ("," <OBJECT>)* ")" "=" ("undefined" | <OBJECT>) ";"

<NUMERIC2>::=<NUMERIC>"(" <OBJECT> ("," <OBJECT>)* ")" "=" <NUMBER> ";"

<GOAL> ::= "Goal" "{" <SUBGOALS>* "}"

<SUBGOALS> ::= <SUBGOAL>*

<SUBGOAL> ::= (<PREDICATE_SUBGOAL> | <FUNC_SUBGOAL> ) ( "[" <NUMBER:deadline> "]" )? ";"

<PREDICATE_SUBGOAL> ::= <PREDICATE> "(" <OBJECT> ("," <OBJECT>)* ")"

<FUNC_SUBGOAL>::= <FUNCTION> "(" <OBJECT> ("," <OBJECT>)* ")" "==" ("undefined" | <OBJECT>)

<TYPE> ::= <ID>

<OBJECT> ::= <ID>

<PREDICATE> ::= <ID>

<FUNCTION> ::= <ID>

<NUMERIC> ::= <ID>

<VAR> ::= <ID>

<ID> = [a-zA-Z][a-zA-Z0-9_]*

<NUMBER> = [0-9]+(.[0-9]+)?

References : Papers and Presentation Material

Published Papers

[1] Éric Beaudry (2011). Planification d'actions concurrentes sous incertitude. Ph.D. Thesis. [Chapter 1 in English].
[2] Éric Beaudry, Froduald Kabanza and François Michaud. Planning for Concurrent Action Executions Under Action Duration Uncertainty
Using Dynamically Generated Bayesian Networks. In Proc. of the International Conference on Automated Planning and Scheduling (ICAPS) 2010.
[3] Éric Beaudry, Froduald Kabanza and François Michaud. Planning with Concurrency under Resources and Time Uncertainty. In Proc. of the European Conference on Artificial Intelligence (ECAI) 2010.

Presentation Material

Slides of my PhD thesis presentation : [English] [Français].

Acknowledgements

Research work on* ActuPlan has been sponsored by National Science and Engenering Reseach Concil of Canada (NSERC) and the Fonds québécois de recherche sur la nature et les technologies (FQRNT).

Related Planners

The following diagram shows a classification of main contributions in in the field of planning with actions concurrency under uncertainty.

Planning Classes

Other related planners are:

DUR of Mausam and Daniel S. Weld (see their JAIR-2008 paper).
FPG of Olivier Buffet and Douglas Aberdeen (see Buffet's web site and their paper in Artificial Intelligence 2009).
Tempastics of Håkan Younes and Reid G. Simmons.
Prottle of Iain Little, Douglas Aberdeen, and Sylvie Thiébaux (AAAI-2005 paper).