About Marvin
Marvin uses FF-Style forward chaining search guided by the Relaxed Planning Graph Heuristic. Like FF, it uses enforced hill-climbing (EHC) search as its first search strategy and falls back to best-first search if EHC fails. There are some subtle differences between the search used in Marvin and that in FF, details of which can be found in the journal paper describing Marvin. The main novel feature of Marvin is its use of Macro-Actions to guide search through plateaux.
Plateaux are areas of the search space where all immediate successors to a given state have been explored and none of these has a heuristic better than its parent. At this point expensive exhauistive search is carried out until a state with a better heuristic value is found. In Marvin, when such a state is found, the sequence of actions from the state at the start of the plateu to the escape point is memorised, and stored as a macro action. We call such sequences plateau escaping macro-actions. When future plateaux are encountered macro-actions are considered for application: the motivation being that plans often contain repeated structure, and if the same sequence of actions can be used again (optionally with different parameters) to escape a further plateau, expensive exhaustive search can be avoided.
Following the competition, Marvin was extended to allow caching of macro-actions between problems in the same domain. A macro-action learnt on one problem can be stored and later re-used in solving another problem. Several techniques were explored for determining which macro-action should be kept. For details of these see the ICAPS paper on Marvin.
Marvin supports the following features of PDDL2.2:
- STRIPS
- ADL
- Derived Predicates
It does not support fluents or temporal planning.
Papers about Marvin
For a full description of the working of Marvin, see the following publications:
"Marvin: A Heuristic Search Planner with Online Macro-Action Learning." A. I. Coles and A. J. Smith. Journal of Artificial Intelligence Research. vol. 28. February 2007. pp. 119--156. Download PDF (BibTeX)"Online Identification of Useful Macro-Actions for Planning." A. I. Coles, M. Fox, and A. J. Smith. Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 07). September 2007. Download PDF (BibTeX)
"Online Generation and use of Macro-Actions in Forward-Chaining Planning" A. J. Smith. PhD thesis, University of Strathclyde, UK. 2007. Download PDF (BibTeX)
Source Code
The source code for the latest version of Marvin can be found here here and a precompiled Linux-i386 binary can be found here. This includes the features described in the ICAPS 07 paper allowing Marvin to cache macro-actions for use in future problems. We recommend that when running this version of Marvin with the caching option (-l) you create a directory to run it in: it writes the macro-actions found for each problem to the current working directory and can thus generate a lot of files.
The source code for Release 1 of Marvin can be found here; a precompiled Linux-i386 binary can be found here. The code is effectively the same as that used in IPC4 but has had a few bug fixes and efficiency improvements made to it, as well as being generally tidied up for release. Note this version does not support storing macro-actions between problems, nor can it load in macro actions from a file. There are some known compilation issues for this version with modern compilers, we therefore recommend you use the latest release.
Building Marvin
Latest Release
Build prerequisites: bison, flex, perl, cmake, the GNU C++ compiler
Marvin is built using cmake. For those unfamiliar with this, make sure cmake is installed on your system, e.g.:
sudo apt-get install cmakeThen download the marvin source code and run:
tar -zxvf marvin2.tar.gz mkdir marvinbuild cd marvinbuild cmake ../marvin2 -DCMAKE_BUILD_TYPE=Release make
Once make has finished, the marvinbuild directory will contain a binary, marvin.
Release 1
There are two ways to build Marvin Release 1, the easiest is to type, in the src directory:
g++ -O3 -fomit-frame-pointer -o marvin
allsources.cpp
If you want to set up a Makefile
./configure
make
and, if all goes well, src/marvin is the binary you need.
Using Marvin
./marvin [OPTION] domainfile problemfile
Notes for latest release
Options are as for version 1 except that:Reduced instance macro computation has been removed from this version of the planner (as this was disabled for generation of all published results). This is equivalent to running version 1 with -r.
Running Marvin with a third parameter, the filename of a list of macro actions, will result in Marvin using the macro actions in this file. The file format is detailed below. This file will not be overwritten or edited by the planner unless -l is also used.
./marvin [OPTION] domainfile problemfile macrolist
-l will force Marvin to save macro-actions after running on each problem (N.B. this creates many files in the current working directory). By default -l will keep all macro actions generated by marvin in the library, sorted by the number of times each macro has been used (most used is considered first). The library will be updated (i.e. overwritten) each time the planner runs, with new macro-actions and an updated ordering.
-n<num> Keep only the n most used macro-actions after each problem (this can only be used in conjunction with -l)
-u<num> Keep only macro-actions used in solving one of the last num problems (this can only be used in conjunction with -l)
Experimentation has shown -l -n10 to be the configuration that solves problems most quickly in general (See publications, ICAPS 07 and thesis, for details); although best results on a given domain vary.
Notes for version 1
Options are:
-b Go straight for best-first search - skip EHC step
Normally Marvin attempts to solve the problem using Enforced
Hill-Climbing, resorting to Best-First
Search if this fails. If you know that EHC will fail on your problem
then pass this option to make it
go straight into trying BestFS.
-m Do not memoise plateau-escaping action sequences
Disable the memoisation of plateau-escaping action sequences.
-p Disable symmetric action choice pruning
Do not prune the number of actions applicable in a given state by only
considering actions applying to
one exemplar in each symmetry group.
-r Do not solve reduced instance prior to specified
problem
Skip the step which produces a reduced instance of the original problem
and attempts to solve that
first. This step is automatically skipped if the reduced problem isn't
any smaller.
-s Sequential (implicit if domain contains derived
predicates)
Do not attempt to plan actions concurrently.
-t Do not recognise transformational operators (implies -r not
being passed)
Do not attempt to recognise simple transformation operators.
-v Verbose
Be verbose about the planning process.
Macro Action Format for Marvin
When asked to cache problems (using the -l flag) Marvin stores its macro actions in an expanded format, rather than compressing them in to PDDL. These are stored in files called macrolist (where xxxxxxxxx is a number string to prevent file overwriting). The file format used by Marvin to do this is described below: index of the next actionname of the next actionnumber of parameters this action hasof the macroof the macro| 5 | number of parameters the macro action has | |
| driver | type of parameter 0 | |
| truck | type of parameter 1 | |
| obj | type of parameter 2 | |
| location | type of parameter 3 | |
| location | type of parameter 4 | |
| 2 | number of time steps in the macro action* | |
| 1 | number of unit actions in this time step* | |
| 0 | ||
| drive-truck | ||
| 4 | ||
| 1 | index in macro parameters of the first parameter of this action, i.e. param 0 of drive-truck should be bound to param 1 of the macro | |
| 4 | ditto for second parameter: param 1 of drive-truck should be bound to param 4 of the macro | |
| 3 | ditto for third parameter: param 2 of drive-truck should be bound to param 3 of the macro | |
| 0 | ditto for third parameter: param 3 of drive-truck should be bound to param 4 of the macro | |
| 1 | number of unit actions in this time step* | |
| 1 | index of the next action | |
| unload-truck | name of the next action | |
| 3 | number of parameters this action has | |
| 2 | index in macro parameters of the first parameter of this action i.e. param 0 of unload-truck should be bound to param 2 | |
| 1 | ditto for second parameter: param 1 of unload-truck should be bound to param 1 | |
| 3 | ditto for third parameter: param 2 of drive-truck should be bound to param 3 of the macro |
*The 'number of time steps in this macro' and 'number of unit actions in this time step' are present as Marvin can handle concurrency in Macro-Actions (despite being non-temporal). If creating macros by hand, for sequential Macros set the number of time steps to the number of actions in the macro, and set the number of unit actions in this time step to 1. To put multiple actions in the same time step simply follow the complete defition of the first action immediately with that at the second, starting from index of the next action.
The macrolist file given to the planner contains the filenames of all the macro-actions to be used in the current problem. The format of the this file is as follows.
| 3 | Number of macros in the file |
| macro.137029448 | File name of first macro action |
| 0 | Number of problems solved since this macro was last used |
| 600 | Number times in total this macro-action has been used |
| macro.137119240 | File name of next macro action |
| 0 | Number of problems solved since this macro was last used |
| 600 | Number times in total this macro-action has been used |
| macro.137134776 | File name of next macro action |
| 0 | Number of problems solved since this macro was last used |
| 23 | Number times in total this macro-action has been used |
The number of times since use, and total use count are used by the planner internally to sort the macro-actions, by default it will consider the most used macro-actions first; if using -u the most recently used will be considered first (ties broken on use count and then arbitrarily). They will not be updated unless -l is used.
Contact Us
If you have any comments or complaints about Marvin then feel free to contact Andrew Coles or Amanda Coles.
Note:
By releasing this code we imply no warranty as to its reliability
and its use is entirely at your own risk.