Marvin

Marvin is a domain-independent forward-chaining heuristic-search planner that participated in the Fourth International Planning Competition.

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:

"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 cmake

Then 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

./configure

make

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

Notes for version 1

-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

*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.

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.