Modules and PlannersLink

PlannersLink

Planners by default use the FD parser. A version of each planner exist using FF parser instead. 3 planners where submitted to Satisficing and Agile track in IPC 2014.

They support action costs and Conditional Effects. See Documentation#Parsers_Supported to know how to tell the parser to ignore or account for action costs.

FFLink

FF planner as described in JAIR 2001. Goal agenda is not computed by default.

FF-parser

planners/ff-ffparser

Command: ./ff --domain <domain_file> --problem <problem_file> --output <plan_output>

Options::
  --help                Show help message
  --domain arg          Input PDDL domain description
  --problem arg         Input PDDL problem description
  --output arg          Output file for plan

BFS_fLink

Greedy Best First Search Planner that uses f(n) = novelty(n), breaking ties with lm_count(n) and h_rel_plan(n). described in Lipovetzky et al. at ECAI 2012

FD-parser

planners/bfs_f

Command: 
./bfs.py <domain_file> <problem_file> <plan_output>

Ignores costs:
./bfs_f_unit_cost.py  <domain_file> <problem_file> <plan_output>

Options specified inside the script

FF-parser

planners/bfs_f-ffparser

Command: ./bfs_f --domain <domain_file> --problem <problem_file> --output <plan_output>

Options::
  --help                          Show help message
  --domain arg                    Input PDDL domain description
  --problem arg                   Input PDDL problem description
  --bound arg (=2)                Max width w for novelty (default 2)
  --output arg                    Output file for plan
  --one-ha-per-fluent arg (=0)    Extract only one helpful action per fluent
  --use-original-ff-heur arg (=0) Use original FF heuristic computed by layers

Anytime BFS_fLink

Runs First SIW, then BFS_f with the bound found by SIW, and finally an anytime version using RWA* described in IPC 2014 Booklet

FD-parser

planners/at_bfs_f

Command: 
./at_bfs.py <domain_file> <problem_file> <plan_output>

./at_bfs_f-2-no-bfs_f.py <domain_file> <problem_file> <plan_output>

./at_bfs_f-2-no-siw.py <domain_file> <problem_file> <plan_output>

./at_bfs_f-no-siw-no-bfs_f.py <domain_file> <problem_file> <plan_output>

Options specified inside the script

FF-parser

planners/at_bfs_f-ffparser

Command: ./at_bfs_f --domain <domain_file> --problem <problem_file> --output <plan_output>

Options::
  --help                       Show help message
  --domain arg                 Input PDDL domain description
  --problem arg                Input PDDL problem description
  --iw-bound arg (=2)          Max width w for SIW (default 2)
  --max-novelty arg (=2)       Max width w for novelty heuristic in BFS(f) 
                               (default 2)
  --output arg                 Output file for plan
  --one-ha-per-fluent arg (=0) Extract only one helpful action per fluent
  --disable-siw arg (=0)       Disable SIW stage
  --disable-bfs-f arg (=0)     Disable BFS(f) stage

Iterative Width is a blind search planner that exploits the low width of classical benchmark when goals are atomic. For conjuctive goals look at SIW, SIW+ or DFS+ described in Lipovetzky et al. at ECAI 2012

FD-parser

planners/iw

Command: 
./iw.py <domain_file> <problem_file> <plan_output>

Options specified inside the script

FF-parser

planners/iw-ffparser

Command: ./iw --domain <domain_file> --problem <problem_file> --output <plan_output>

Options::
  --help                Show help message
  --domain arg          Input PDDL domain description
  --problem arg         Input PDDL problem description
  --bound arg (=1)      Max width w for IW(w)
  --atomic arg (=1)     Runs IW(w) over each atomic goal of the problem (bool)
  --output arg          Output plan file

IW PlusLink

IW+ relaxes IW novelty pruning. described in Lipovetzky et al. at ECAI 2014

FD-parser

planners/iw

Command: 
./rp_iw.py <domain_file> <problem_file> <plan_output>

Options specified inside the script

FF-parser

planners/iw-ffparser

Command: ./rp_iw --domain <domain_file> --problem <problem_file> --output <plan_output>

Options::
  --help                Show help message
  --domain arg          Input PDDL domain description
  --problem arg         Input PDDL problem description
  --bound arg (=2)      Max width w for IW(w)
  --output arg          Output plan file

SIWLink

Serialized Iterative Width is a blind search planner competitive that exploits the low width of classical benchmark through IW and simple goal serialization described in Lipovetzky et al. at ECAI 2012

FD-parser

planners/siw

Command: 
./siw.py <domain_file> <problem_file> <plan_output>

Ignores costs:
./siw_unit_cost.py  <domain_file> <problem_file> <plan_output>

Options specified inside the script

FF-parser

planners/siw-ffparser

Command: ./siw --domain <domain_file> --problem <problem_file> --output <plan_output>

Options::
  --help                Show help message
  --domain arg          Input PDDL domain description
  --problem arg         Input PDDL problem description
  --bound arg (=1)      Max width w for IW(w)
  --output arg          Output plan file

SIW PlusLink

SIW+ relaxes IW novelty pruning. Blind Search Planner with high performance, closer to FF over IPC\'11 benchmark described in Lipovetzky et al. at ECAI 2014

FD-parser

planners/siw_plus

Command: 
./siw_plus.py <domain_file> <problem_file> <plan_output>

Ignores costs:
./siw_plus_unit_cost.py  <domain_file> <problem_file> <plan_output>

Options specified inside the script

FF-parser

planners/siw_plus-ffparser

Command: ./siw_plus --domain <domain_file> --problem <problem_file> --output <plan_output>

Options::
  --help                Show help message
  --domain arg          Input PDDL domain description
  --problem arg         Input PDDL problem description
  --bound arg (=1)      Max width w for IW(w)
  --output arg          Output plan file

DFS PlusLink

DFS+ Extends SIW+ Goal serialization. Blind Search planner with high performance, closer to LAMA\'11 and BFS_f over IPC\'11 benchmark described in Lipovetzky et al. at ECAI 2014

FD-parser

planners/dfs_plus

Command: 
./dfs_plus.py <domain_file> <problem_file> <plan_output>

Ignores costs:
./dfs_plus_unit_cost.py  <domain_file> <problem_file> <plan_output>

Options specified inside the script

FF-parser

planners/dfs_plus-ffparser

Command: ./dfs_plus --domain <domain_file> --problem <problem_file> --output <plan_output>

Options::
  --help                Show help message
  --domain arg          Input PDDL domain description
  --problem arg         Input PDDL problem description
  --bound arg (=2)      Max width w for IW(w)
  --output arg          Output plan file

Generic BFS with Optional HeuristicsLink

By default BFS is set to GBFS

FF-parser

planners/generic-best_first-ffparser

Command: ./bfs --domain <domain_file> --problem <problem_file> --output <plan_output>

Options::
  --help                Show help message
  --domain arg          Input PDDL domain description
  --problem arg         Input PDDL problem description
  --heuristic arg (=1)  1: H_add (default 1)
                        2: H_add_Rp
                        3: H_max_Rp
                        4: H_add_FF_Rp
                        5: H_max_FF_Rp
                        6: H_layered_FF_Rp ( FF_*, as in Journal Paper)
  --anytime arg (=0)    Anytime (default False)
  --output arg          Output file for plan

Search Algorithms ImplementedLink

All Search Algorithms implement Forward Search by accessing

 interfaces/agnostic/fwd_search_prob.hxx

decoupling the search algrotihm from successor generation, applicability function, etc. Intended to easily run this algorithms on backward search.

No use of heuristics.

Breadth-First searchLink

 include/aptk/brfs.hxx

Width-Based SearchLink

described in Lipovetzky et al. at ECAI 2012, and Lipovetzky et al. at ECAI 2014

Iterated WidthLink

Breadth-First search with novelty pruning.

 include/aptk/iw.hxx

Iterated Width PlusLink

Breadth-First search with a relaxed novelty pruning.

 include/aptk/rp_iw.hxx

Serialized Iterated WidthLink

Uses iterated width to both solve and serialize the goals. The serialization is a form of Hill-Climbing over the set of goals

 include/aptk/siw.hxx

Serialized Iterated Width PlusLink

Uses iterated width plus to both solve and serialize the goals. The serialization is a form of Hill-Climbing over the set of goals

 include/aptk/siw_plus.hxx

Depth-first Search WidthLink

Uses iterated width to both solve and serialize the goals. DFS in the space of serialization induced by bounded Iterative Width.

 include/aptk/dfs_plus.hxx

Heuristic SearchLink

Best-First searchLink

Greedy Best First SearchLink

 include/aptk/at_gbfs.hxx

Any-time Best First SearchLink

 include/aptk/at_bfs.hxx

Any-time Best First Search with two open listsLink

 include/aptk/at_bfs_dq.hxx

The PREFERRED list, for nodes generated by preferred operators, and the OPEN list, for the rest.

Best First Search with three open lists and two heuristic estimatorsLink

include/aptk/at_bfs_dq_mh.hxx

The search frontier is split into three lists:

BOTH: holds nodes generated by actions deemed as \'preferred\' by both heuristic

estimators

PREFERRED: holds nodes generated by actions deemed as \'preferred\' by the

primary heuristic estimator

OPEN: holds nodes generated by actions not deemed as \'preferred\' by the primary

heuristic estimator

Any-time Weighted A*Link

Weight W decaying according to fixed decay parameter. Variants include single queue and multiple queue (either with one or two heuristic estimators).

include/aptk/at_wbfs.hxx
include/aptk/at_wbfs_dq.hxx
include/aptk/at_wbfs_dq_mh.hxx

Any-time Restarting Weighted A*Link

described in Ricther et al. at ICAPS 2010 with weight W decaying according to fixed decay parameter. Variants include single queue and multiple queue (either with one or two heuristic estimators).

include/aptk/at_rwbfs.hxx
include/aptk/at_rwbfs_dq.hxx
include/aptk/at_rwbfs_dq_mh.hxx

Contract SearchLink

The Deadline Aware Search algorithmLink

described in Dionne et al. at SOCS 2011

include/aptk/das.hxx

EHCLink

Enforced Hill Climbing as in JAIR 2001.

include/aptk/ff_ehc.hxx

Heuristics ImplementedLink

Critical PathsLink

h\^1Link

interfaces/agnostic/h_1.hxx

h\^2Link

interfaces/agnostic/h_2.hxx

Delete RelaxationsLink

h_max / h_addLink

Same implementation as h\^1. h_add and h_max differ only through the evaluation function, which can be specified. Dijskstra Based implementation

interfaces/agnostic/h_1.hxx

Relaxed Planning Graph implementation

interfaces/agnostic/layered_h_max.hxx

h\^ffLink

Original FF heuristic computation from JAIR 2001 paper

interfaces/agnostic/ff_rp_heuristic.hxx

Relaxed Planning Graph HeuristicsLink

Computes relaxed plan heuristics backwards from the goal based on best_supporters function. Keyder et al. ECAI 2008 h_1 and h_add natively define best supporters, although other heuristics could be used too.

interfaces/agnostic/rp_heuristic.hxx

h\^CLink

Semi Relaxed Heuristic by introducing special fluents that explicitly represent conjunctions of fluents Keyder et al. ICAPS 2012

interfaces/agnostic/h_C.hxx

Counting heuristicLink

Unachieved GoalsLink

Counts the number of unachieved goals

interfaces/agnostic/h_unsat.hxx

Unachieved LandmarksLink

Counts the number of unachieved landmarks. Landmark graph is built from And/Or Graphs Keyder et al. ECAI 2010

interfaces/agnostic/landmark_count.hxx

NoveltyLink

Counts the size of the smallest tuple made true by a given state for the first time in the search Lipovetzky et al. at ECAI 2012

interfaces/agnostic/novelty.hxx

Novelty PlusLink

Relaxed versioin of Novelty Lipovetzky et al. at ECAI 2014

interfaces/agnostic/novelty.hxx

ReachabilityLink

Naive implementation for testing reachability

interfaces/agnostic/reachability.hxx

Watchlist-based implementation for testing reachability:

interfaces/agnostic/watch_list_succ_gen.hxx

(see the \"is_reachable(const State&)\" method)

Parsers SupportedLink

We currently ported FF-Parser and FD-Parser

FF ParserLink

FF-Parser is based on bison and flex. It\'s compiled as an independent library in

external/libff

and connected to the toolkit in

interfaces/ff-wrapped/ff_to_aptk.hxx
interfaces/ff-wrapped/ff_to_aptk.hxx

creating a STRIPS Problem instance.

Action costs can be ignored by setting the ignore_action_costs = true

void get_problem_description(  std::string pddl_domain_path,
                    std::string pddl_problem_path,
                    STRIPS_Problem& strips_problem,
                    bool ignore_action_costs = false,
                    bool get_detailed_fluent_names = false );

aptk::FF_Parser::get_problem_description(...,true)

FD-parserLink

FD-Parser is written in python. It\'s located in

external/fd

and connected to the toolkit in

planners/python/agnostic/py_strips_prob.hxx
planners/python/agnostic/py_strips_prob.cxx

creating a STRIPS Problem instance.

Action costs can be ignored by setting in your python script

task.ignore_action_costs = True

as it\'s done for example in

/planners/bfs_f/bfs_f_unit_cost.py

Problem Representation (STRIPS Model)Link

STRIPS Problem and useful information like mutexes (if computed)Link

interfaces/agnostic/strips_prob.cxx  
interfaces/agnostic/strips_prob.hxx

STRIPS StatesLink

interfaces/agnostic/strips_state.cxx    
interfaces/agnostic/strips_state.hxx

Actions and FluentsLink

interfaces/agnostic/fluent.cxx  
interfaces/agnostic/fluent.hxx

interfaces/agnostic/action.cxx  
interfaces/agnostic/action.hxx

interfaces/agnostic/cond_eff.cxx    
interfaces/agnostic/cond_eff.hxx

Successor GeneratorLink

interfaces/agnostic/succ_gen.cxx
interfaces/agnostic/succ_gen.hxx

Running ExperimentsLink

Scripts for running experiments, profiling, benchmarking and creating tables with Coverage, IPC Time and Quality Score are available

benchmarks/run.py

# Dependencies/Prerequisites:
#   - valgrind
#   - timeout
#   - dot (graphviz)
#   - krtoolkit

 Usage:
    python run.py profile <executable> <ipc directory> [<domain pddl> <problem pddl>]
    python run.py benchmark <executable> <ipc directory> <results directory> [<domain>]
    python run.py compare <directories with , separated> <ipc directory>
    python run.py clean

Some Benchmark domains can be found at

benchmarks/ipc-2006/
benchmarks/ipc-2011/
benchmarks/ipc-2014/

To use run.py script over new sets of benchmarks instead of specific domains, edit

benchmarks/domains.py

ExamplesLink

FF-Interface ExampleLink

The example for the 'ff parser' interface can be found on

* examples/ff-interface

FD-Interface ExampleLink

The example for the 'fD parser' interface can be found on

* examples/fd-interface

This is a very simple example that shows the basics for interfacing lwaptk with Fast Downward parser. In order to build the example issue the command:

$ ./build.py

and to run the example:

$ ./parser.py <path to pddl domain file> <path to pddl problem file>

if everything is working as it should, you should see FD parsing output on the standard output, as well as a dump of the grounded actions.

Note that this will copy the folder externals/fd to the local directory, so DO NOT add it to the repository. If you need to do customize Fast Downward parsing scripts, just edit build.py to avoid it clobbering your local copy.

Agnostic Interface ExamplesLink

The examples for the 'planner agnostic' interface can be found on

examples/agnostic-examples

and cover the following topics:

Assembling STRIPS problem programaticallyLink

Shows how to define a STRIPS planning problem programatically.

* agnostic-examples/assembling_strips_problems

Successor GeneratorsLink

Discusses and compares different ways of generating successors during search.

* agnostic-examples/successor_generation

Open ListsLink

Discusses and compares different ways of creating open lists for your search algortithm.

* agnostic-examples/fibonacci_open

BFS engine variationsLink

Shows how can one assemble available components to deliver a planner built around a BFS search engine, with multiple queues and secondary heuristics, on a parametrized planning task.

* agnostic-examples/bfs
* agnostic-examples/bfs-double-queue 
* agnostic-examples/bfs-double-queue-secondary-heuristic

BFS + h_max (greedy|delayed|anytime) + FF-parserLink

Shows how to assemble a classic planner: best-first search using h_max with multiple modes: greedy/delayed/anytime, over a task specified in PDDL and parsed by FF-parser

* agnostic-examples/bfs-hmax

WA* variations + landmarksLink

Shows how can one assemble available components to deliver a planner built around a WA* search engine, with multiple queues and secondary heuristics, on a parametrized planning task. Illustrates as well how to use landmark count heurstic.

* agnostic-examples/wa-planner
* agnostic-examples/rwa-planner

Deadline Aware Search engineLink

Shows how can one assemble available components to deliver a planner built around Deadline Aware Search.

* agnostic-examples/das

Breadth-First search + FF-parserLink

Shows how can one assemble available components to deliver a blind search planner.

* agnostic-examples/brfs

h_C compilations + FF-parserLink

Shows how can one use the \Pi_C compilation to compute the h_C heuristic. Keyder et al. ICAPS 2012

* agnostic-examples/h_C_heuristics

Replanner (changing init and goal situation on the fly)Link

Shows how to create a replanner. It illustrates how to change the initial and goal states without having to parse the problem again, solving it with bfs+h_max. In the example we change the initial and goal situations by applying the first action of the current plan to progress the initial state, and last action of the plan to regress the goal.

* agnostic-examples/replanner

Width-Based algorithm + FD parserLink

Shows how SIW is implemented, using novelty function and FD parser

* planners/siw