SHOP3

This repository contains the open source version of the SHOP3 Hierarchical Task Network (HTN) AI planner.

Version 4.1 Release (forthcoming)

Add the ability to use PDDL axioms (:derived-predicates), with an appropriate PDDL requirement mixin.

Related to adding this support, identified a number of issues with translation of PDDL domains into SHOP, notably non-deterministic ordering of translation operations that could lead to errors. Some translation methods rewritten from generic functions to conventional functions to address these issues.

Fixed treatment of numeric fluents that do not having initial values specified in the planning problem. These are explicitly permitted by the PDDL specification, but would previously cause SHOP to raise errors.

Incorporated PDDL-UTILS as a dependency. Previously, all PDDL wrangling was done in SHOP-specific code, which was duplicative. Did not replace existing code, but will not continue to add duplicate code when library code is available.

Updated manual.

Version 4.0 was never really released, so there is no account of it here.

Version 3.13 Release (2024-08-18)

This release contains three key new features:

There are buildapp-based command-line executables for SHOP3 that can be built and installed. See the buildapp subdirectory for more details. These are probably not as well documented as could be.
We now use Nicholas Hafner's random-state library for repeatable, portable random number generation, making it easier to do replicable experiments with SHOP3.
We introduced the ability to generate HDDL-format plans from the plan sequences and trees generated by shop:find-plans-stack.

In addition to the above new features, there are also a large number of bug fixes.

Version 3.8.1 Release (2023-01-25)

In support of work I (RPG) have done to add Monte Carlo Tree Search to SHOP3, I have made a number
of minor improvements, bugfixes, etc. These changes are of general interest/value, so they are
now released as version 3.8.1 of SHOP. Descriptions of the changes may be found in the ChangeLog.

License

Mozilla Public License

Installation Instructions

Common Lisp

SHOP3 is written in Common Lisp (CL), and requires a CL
implementation to run. We recommend one of the following
implementations:

SBCL: Steel Bank Common Lisp. Available in packages on Ubuntu
Linux and Mac Homebrew. Also available from sbcl.org.
CCL: Clozure Common Lisp. Available from
clozure.com.
ACL: Allegro Common Lisp: Available from franz.com.
Unlike the previous two implementations, this is a commercial
software product.
LispWorks: Recently we have been given a license to test SHOP3 on
LispWorks, and have verified that the SHOP3 test
suite passes on LW. Like Allegro, LispWorks is a commercial lisp implementation.

We regularly test SHOP3 on all of these lisp implementations,
using an exhaustive test suite. There are at least a handful of
other CL implementations, both open source and commercial, but we have
not tested them with SHOP3. Attempts to run SHOP3 on ECL, ABCL, and clisp
have not been successful. Patches to make SHOP3 work with other
implementations are welcomed, but we have no plans to add support to
any others ourselves.

Note that we have not tested SHOP3 on the free versions of ACL or LispWorks, and
we do not expect it to work well on these platforms because of their resource limitations.
For hobbyist projects, we suggest SBCL or CCL instead.

Obtaining the code

Clone this repository and then initialize and populate the
submodules.

git clone https://github.com/shop-planner/shop3

See the two installation options below to see whether you need to supply
the --recurse-submodules option when cloning.

Once you have done that, you can get SHOP3 started either using
Quicklisp (probably easiest) or by configuring ASDF (the Common Lisp
build manager) yourself. See below.

Option 1: Quicklisp

Probably the easiest way to work with SHOP3 will be to use it in
conjunction with Quicklisp. Quicklisp
is a package manager for CL libraries, and will be the easiest way to
get the libraries that SHOP3 depends on.

If you wish to use Quicklisp, follow the installation instructions for
quicklisp at the above site. Now you have two choices: you can install
SHOP3 through Quicklisp, or you can check out SHOP3 from here (GitHub) and use
Quicklisp only for the required dependencies.

The Easy way -- do everything with Quicklisp

Start CL
Inside CL, enable Quicklisp
Enter (ql:quickload "shop3") into the CL REPL.

With your own copy of SHOP3

This installation method is best for someone who is interested in developing
new HTN planning capabilities with SHOP and will want to be modifying the
source of the planning system. If you would just like to develop planning
domains and problems, then the simpler, all-Quicklisp method is probably
better for you. You can always check out a copy of the repo later if you
want.

Clone the SHOP3 repository into the local-projects subdirectory of your
Quicklisp install directory (see the Quicklisp docs).
Start CL
Inside CL, enable Quicklisp
Enter (ql:quickload "shop3") into the CL REPL.

Quicklisp contains all of the dependencies that SHOP3 requires except the
"pddl-utils" system. This system is only used in the tests, or for some optional
functionality. If you wish to have this subsystem, you can either;

populate the git submodules -- or just the pddl-tools one -- in the SHOP3 git
repository, OR
Clone the pddl-tools repository into
local-projects, as well, and do not bother with the git submodules.

Option 2: Without Quicklisp

The SHOP3 repository has links to all of the libraries it requires in
its git submodules. If Quicklisp is not the right approach for you,
you must use git commands to populate SHOP3's submodules (if you like,
you may clone with the --recurse-submodules option), and then:

Start CL
Load the ASDF CL build
system by doing (require :asdf) in the CL REPL.

Tell ASDF where to find SHOP3:

(asdf:initialize-source-registry
         '(:source-registry (:tree SHOP3-DIRECTORY) :inherit-configuration))

Fill in the name of the directory of your cloned repository for SHOP3-DIRECTORY.

Enter (asdf:load-system "shop3") into the CL REPL.

Once started

We suggest that you interact with SHOP3 through the shop-user
package in the REPL, for exploratory work. If you wish to develop
a more substantial planning application, we recommend starting a new
system in a dedicated package that will :use-package shop3.

The best environment for working with CL for any purpose, including
SHOP3 planning, is through the Superior Lisp Interaction Mode for
Emacs, or SLIME or its fork,
SLY. Both of these are available
for installation through MELPA using the Emacs
package manager.

If you use Allegro Common Lisp, Franz have their own Emacs Lisp Interface (ELI)
as a possible alternative.

Allegro, CCL, and Lispworks each have some
sort of GUI/IDE, as well.

Using SHOP3

See the user manual in the docs directory of the repository.
Building the manual requires having texinfo, and SBCL installed, and
benefits from having tex/latex installed. To build, change to the
docs directory and do make html if you have only makeinfo
installed, or just make if you have tex/latex, as well. This will
produce the manual in HTML, Emacs info, and PDF formats.

Questions

If you have questions, please post them using the Discussions link.

Now that GitHub has added discussions, we would prefer to keep issues for actual bug reports.

Citing SHOP3

The best way to cite SHOP3 is to cite the paper "Hierarchical Task Network Planning in Common Lisp: the case of SHOP3": Goldman, R.P. and Kuter, U. (2019) ‘Hierarchical Task Network Planning in Common Lisp: the case of SHOP3’, in Proceedings of the 12th European Lisp Symposium. European Lisp Symposium, Genova, Italy.

BibTeX:

@inproceedings{GoldmanKuter:SHOP3ELS,
  title = {Hierarchical {{Task Network Planning}} in {{Common Lisp}}: The Case of {{SHOP3}}},
  booktitle = {Proceedings of the 12th {{European Lisp Symposium}}},
  author = {Goldman, Robert P and Kuter, Ugur},
  year = {2019},
  month = apr,
  address = {{Genova, Italy}}
}

shop-planner/shop3