Skip to content
Giuseppe Della Penna

The UPMurphi Planner

The Universal Planner Murphi supports planning and universal planning for linear and nonlinear continuous PDDL+ models with processes and events. UPMurphi also supports Timed Initial Literals and Timed Initial Fluents.

UPMurphi is based on the Discretise and Validate approach and it has been designed to automatically interface with the VAL plan validator.

Warning: this project is no longer maintained. Unfortunately, the Murphi core, which UPMurphi builds on, is rather old and has not been updated, so maintaining UPMurphi would require us a complete rewriting of the base code, which is currently impossible. If you still want to try it, refer to the troubleshoot.txt for the correct versions of the libraries and tools that were used in our last successful compilations. Thanks for your interest in UPMurphi, we hope to come back soon with a new, updated tool.

Quick Start

To quickly begin using UPMurphi, follow these steps.

  • First of all, download the latest UPMurphi distribution package.
  • By default, UPMurphi uses a 32-bit compilation. However, it has been designed to support compilation onto 64-bit architectures, although it has not been fully tested yet. To succesfully compile UPMurphi, make sure you have the required libraries: on Ubuntu you can simply issue the following command: sudo apt-get install build-essential flex bison libc6-dev-i386 gcc-multilib g++-multilib. Similar packages need to be installed in other Linux distributions as well as in Cygwin under Windows.
  • Enter the “src” directory, call “make” and cross your fingers. If everything is ok, the upmurphi compiler (upmc) and the PDDL-to-Murphi compiler (pddl2upm) are now in the “bin” directory.
  • To compile a PDDL domain/problem to an UPMurphi planner, invoke the UPMurphi compiler (upmc): upmc <domain.pddl> <problem.pddl>. This will call several tools (including the g++ compiler) and generate the executable planner, called problem_planner(.exe), as well as other support and intermediate files.
  • Once the executable planner has been generated, you can run it to start the planning process. By default, the planner will allocate 1Gb of memory, search for a feasible plan and write it to the file problem_plan.pddl.
  • If you want to use the VAL validator to automatically validate the generated plans, download and install it separately, then edit the Makefile in the “src/UPMurphi” folder and write the complete pathname of the “validate” binary as the value of the VAL_PATHNAME constant.

For more information about how to download, install and use UPMurphi, follow the links below:

Current Limitations of UPMurphi

UPMurphi requires the PDDL+ domain to be typed for being processed. The only metric currently supported by UPMUrphi is :minimize total-time.

Note that the current version does not use any heuristic search algorithm. Due to the blind search finding a plan may take long, so be patient ;)

Usage Examples

Discretisation of the PDDL+ Model

Assuming you are in the ex/generator directory:

  • From a PDDL+ domain and problem with user specific discretisation settings (timestep 0.5, mantissa digits: 5, exponent digits: 2):
    ../../bin/upmc tank_domain.pddl tank_problem.pddl --custom 0.5 5 2
  • From a PDDL+ domain and problem with default discretisation settings
    ../../bin/upmc planetary_lander.pddl planetary_lander_problem.pddl

Planning and Validating

  • Default settings (search for feasible solution, output PDDL+ plans, 1Gb RAM) with PDDL+ verbose mode (includes comments with values for the state variable):
    ./tank_domain_planner -format:pddlvv
  • Specific Settings (2Gb RAM, plan duration limited to 20 time units):
    ./planetary_lander_planner -m 2000 -tl 20

Papers on UPMurphi

For an updated list of related publications see the papers page.

Changelog

2.0R1: “UPMurphi is born” (21/4/2010)

2.0R2: “A Real Fix” (6/5/2010)

  • FIX: Fixed a memory leak in mu_real.cpp (“name” property now deleted in the class descructor).

2.0R3: “Millions of Rules” (3/6/2010)

  • UPD: The type used to point and index UPMurphi rules is now parametric (declared in mu_prolog.hpp for the planner and mu.hpp for the compiler, of course the two declarations must be identical). It is currently set to unsigned long, while previously it was an unsigned int. This allows us to handle even the billions of rules generated by the house-lifting case study. Warning: this also causes a big increase of memory requirements during the transition graph generation phase.
  • NEW: Exploration progress reports now show the exploration speed, expressed both in rules per second and states per second.

2.0R4: “Remember your Errors” (9/6/2010)

  • NEW: This update makes UPMurphi not to include in the final graph the transitions leading to an error state, i.e., which violate an invariant. Indeed, with the previous “Murphi-like” logic, error states were not expanded, but transitions leading to them were still included in the final system dynamics. To exploit errors during postprocessing, error transitions are now written in a separate file, with “.errors” extension. However, so far this file is never read or used.
  • NEW: Added new text dump method for ENUMs.
  • NEW: Exploration progress reports now show the number of error states encontered so far.

2.0R5: “Better Control” (16/6/2010)

  • FIX: Fixed and optimized the code for the controller generation (format:raw). In particular, now the plan generation phase is skipped if the required output is a binary, textual or compressed controller.
  • FIX: Fixed a couple of errors (hoping that there are no others!) in the UPMurphi compiler which limited the extension of the rule indexes to unsigned long.

2.0R6 “Errors squared” (21/6/2010)

  • FIX: Memory leak found and fixed. Memory increased at each goal or error reached, since in this case the corresponding temporary state was not removed from memory nor queued. An almost invisible effect, unless invariants were massively used.
  • UPD: Modification of the output format: now also in the output modes text, raw (binary controller) and obdd (compressed controller) only rules with PDDL class action or durative_start are written. In this way, rules used internally by the model to simulate other characteristics of the system can be classified as events and not appear in the controller.

2.0R7 “Longer (f)seeks” (28/6/2010)

  • NEW: Introduced in OutputManager class the static function lfseek, called in place of fseeks (in particular on the reachables file) that may require offsets larger than an unsigned long.
  • NEW: Added the number of controller actions to the properties file (.properties), eliminating the need to manually recalculate it though a division on the value returned by ftell (which could lead to an overflow!).
  • UPD: Reorganization of the code: part of the classes in upm_system have been moved to the new files upm_storage and upm_graph.
  • DEL: CUDD distribution was removed from UPMurphi. To use the OBDD compression (experimental) is now necessary to download and install CUDD manually in the cudd/ directory inside the UPMurphi root.

2.0R8 “Disk Graph” + “Malicious Sort” (7/7/2010)

  • FIX: Critical bug! The hash-campacted hash table insertion algorithm of the original Murphi is actually smarter than it seems. Indeed, while inserting new elements (state signatures), it keeps ordered (in descending order w.r.t. signature values) the collision lists associated with each ht slot. This is done by a very subtle code inside the “search for an empty slot” loop. In the previous versions of UPMurphi, particular state schemes, hash function seeds and a crowded table could lead to an incorrect state-signature/state-index association, since the indexes weren’t reordered with the corresponding signatures. In other words, UPMurphi could overlap two distinct states, ending in a different transition graph. This would often not affect the plan synthesis, but its optimality (and the number of controlled states). After three days of in-depth debugging of the ht logic, the problem was solved.
  • NEW: The StateGraph class, which represents the system transition graph, has been split in two implementations: a memory-image implementation, nearly identical to the previous one, and an indexed-disk-image, which (as the name suggests) stores (as efficently as possible) the graph on disk. As a consequence, UPMurphi now can load and analyze HUGE transition graphs. The better is that you haven’t to choose which implementation to use: UPMurphi will estimate the memory needed by the transition graph during the state space exploration, and select the most suitable representation.
  • UPD: Timestamps in reports are now written in a more human-friendly hh:mm:ss format :)
  • NEW: Added the number of errors to the properties file (.properties).
  • UPD: Rules in rulesets are now correctly written in PDDL as parametric actions.

2.0R9 “CSV controller” (17/11/2010)

  • NEW: Added the CSV output format (switch -format:csv), which writes the controller actions in a user-friendly but still machine-readable fashion using comma separated values. The controller state-action pairs are written one per line, and each line contains the state variables and their values (in the form name: value), separated by a semicolon and followed by the rule (action) name. Note that only the state variables marked with a pddlname are printed.

2.0R10 “Calculated attributes” (12/02/2013)

  • FIX: Critical bug! Rule weights and durations were recalculated when needed (e.g., during optimal paths calculation and plan generation), but in this way state-dependant values (i.e., calculated through an expression on the current state variables) had incorrect values. The solution is to calculate the rule weight and duration during the state space expansion and write them to the .transitions file together with the corresponding transition, so they don’t need to be recalculated anymore. However, this requires more memory and disk space. Therefore, the two new –varweight and –varduration switches have been added to the UPMurphi compiler (upmc) command line. If specified, they declare that the model uses state-dependant expressions to evaluate the rule weight and duration, respectively. In this way, the not-state-dependant values continue to be recalculated “on the fly”, saving memory. Warning: if you use state-dependant expressions but do not specify the corresponding switch on the upmc command line, the planning results will be incorrect.

3.0 “Integration” (13/04/2015)

  • NEW: integrated PDDL parsing. Now upmc can process a pre-built model file (.m) as well as a pair of (domain,problem) pddl files.
  • NEW: upmc options –prompt and –custom X Y Z passed to the PDDL parser
  • NEW: automatic compilation of executable planner with g++ (can be skipped with –noexec)
  • NEW: debug mode planners (step-execution of rules) with the –debug option
  • FIX: correct pddl output (syntax of timestamps and durations)
  • CHG: now planner output is always written to a file (if not specified, the problem name is used to derive the output filename), and can be optionally displayed also on stdout with the -print option
  • CHG: default memory for planner is now 1Gb
  • CHG: bit compression and hash compaction are now defaults in upmc
  • NEW: “domain” and “problem” keywords in model files to link the model to the source pddl files
  • NEW: automatic plan validation using VAL (-val)
  • NEW: makefile defines to configure planner compilation and plan validation switches
  • NEW: automatic pathname discovery for include and bin directories (UPMURPHI_HOME should not be needed any more in default installations)
  • NEW: closed hash table full no longer breaks the computation if at least one goal state has been reached
  • NEW: “message” keyword in model file to include messages in the planner output
  • NEW: Planning task summary at the beginning of the planner’s output
  • NEW: real constant T in the model file is now automatically recognised as the model time quantum
  • NEW: real variable TIME in the model file, if present, is used to measure the plan length
  • NEW: if plan length is available, the new option -tl allows to limit the length of the plans
  • FIX: 64 bit filesystem g++ compiler option added to the planner compilation switches
  • NEW: compiler warnings are suppressed by default (use –warnings to show them)
  • CHG: experimental OBDD extension removed from the release