Planning at King's

  • Increase font size
  • Default font size
  • Decrease font size
Home CRIKEY

CRIKEY: A Temporal Planner Supporting Co-ordination

E-mail Print PDF

CRIKEYThe original CRIKEY! is a temporal planner, written by Keith Halsey, in 2002-4, as his PhD project under the supervision of Maria Fox and Derek Long. The motivation behind CRIKEY! was to develop a planner capable of reasoning with domains using PDDL 2.1 durative actions, without the restriction that the actions are specified with a TGP-style semantics. It participated in the fourth international planning competition (IPC4) in 2004, but only domains using a compilation of timed initial literals (TILs) allowed it to display these abilities.

Notably, it was the only planner able to produce results in the compiled TIL domains, other than SGPlan 4, which avoided the reasoning necessary in the general case by detecting TIL actions used in the competition domains and planning accordingly (indeed, renaming the actions breaks this detection and causes invalid plans to be produced). See below for an interesting collection of domains in which PDDL 2.1 semantic durative actions are used.

 

An extensive paper describing CRIKEY can be found here. Please refer to this paper if you use the original CRIKEY system.

More recent work, carried out jointly between Andrew and Amanda Coles, Derek and Maria, has redeveloped CRIKEY as CRIKEY3. A number of improvements were made upon the original design of CRIKEY, including native support for timed initial literals, a new temporal relaxed planning graph and support for self-overlapping actions (e.g. '(fell-timber location2)' can occur in parallel with itself). Details of these changes are described in our 2008 AAAI paper. Please refer to this paper if you use the CRIKEY3 system.

Download

Please note that, in terms of capabilities, CRIKEY3 (and the earlier CRIKEY system) has been superseded by two subsequent planners built on the CRIKEY3 code base.

  • COLIN which introduces support for linear continuous numeric change and duration-dependent effects
  • POPF which avoids many of the overheads incurred through splitting actions by using a forward search over a partial-order rather than a total-order.

If, however, you still wish to download and run either of the older CRIKEY systems, they are available below:

Click here to download CRIKEY as a ready-to-run Java JAR, which also contains the source code. You will need to select the Files tab, then select Crikey, then select Crikey2.

Click here to download CRIKEY3 - both a source .tar.gz and a statically-linked binary for x86 machines are provided.

Usage

CRIKEY!

CRIKEY! supports most of PDDL 2.1 (durative actions, fluents) but not ADL. To execute it, type:

java -jar CRIKEY.jar domainFile.pddl problemFile.pddl [outputfile.soln] [max plan length]

The last two parameters are optional.

Alternatively, if you have unpacked the jar, set the CLASSPATH variable to the directory in which you unpacked the jar and then execute:

java crikey.CRIKEY ....

CRIKEY3

CRIKEY3 supports most of PDDL 2.2 (durative actions, fluents, TILs) but not ADL or derived predicates. To execute it, compile it and type:

./crikey3 domain.pddl problem.pddl

Domains

Download Domains (temporaldomains.tar.gz)

The set of domains included in this domain archive were produced by Keith Halsey. Their purpose was to demonstrate the functionality of CRIKEY on domains where the concurrent execution of actions is essential to find propositionally sound plans. Such domains cannot be successfully handled by planners using the TGP style compilation of temporal actions into single STRIPS actions: the ability to perform another action between the start and end of a temporal action is essential in finding a solution to these problems.

The Match Domain

First introduced by Fox and Long in 2003, the match domain is concerned with fixing a fuse in a cellar. An electrician can only fix one fuse at a time. In order to fix a fuse light must be present, this can be achieved by striking a match. The action of lighting a match adds the predicate that there is light, at the end of the durative light-match action the fact that there is now light is deleted. It is, therefore, necessary to begin the execution of the light match action and fix the fuse during its execution in order to solve the problem. Compiling the domain using the TGP style semantics creates a light match action that both adds and deletes the fact that there is light. Applying add effects before delete effects (as the PDDL semantics demand) results in planners reporting no solution exists; doing the reverse results in the production of invalid plans.

The Lift Match Domain

This is an extension of the match domain. The same basic problem exists, that is the fuses must be mended during the burning of a match; however, the domain is extended to include some other activity which does not necessarily require concurrent execution of actions. The fuses are distributed around rooms, electricians must navigate these rooms using lifts and corridors. This domain does not introduce any new concurrency requirements over the standard match domain, it simply creates a bigger planning problem, demonstrating the use of both required concurrency and conventional planning.

The Variable Durations Match Domain

Another variant of the match domain, designed to introduce variable durations as fluents. Fuses take different times to fix and different matches also burn for different durations. A fuse that takes a long time to fix must be fixed by the light of a match that burns for a sufficient amount of time. This match must therefore not be wasted on another shorter fuse. The light match action is changed so that only one match can be alight at any one time. This makes it advantageous to fix as many fuses as possible by the light of one match, in order to minimise the temporal length of the plan. This variant is effectively a bin packing problem. Fluents are used to model the burning time of the match and the mending time of the fuse.

The Driverlog Shift Domain

This is an extension of the driverlog domain used in IPC 3. In the standard form drivelog involves moving packages around cities using trucks and drivers to transport them. The driverlog shift domain adds the constraint that drivers can only work for a certain amount of time before they must take a break and have a rest. This requires actions to be scheduled concurrently, as the shift action is an envelope, into which must fit the contents of driving and walking.

The Mousetrap Domain

This domain is inspired by the board game of the same name. Mice must navigate around a maze to find and eat cheese. Travelling down some routes can trigger devices to activate. These devices trigger further devices (in a cartoon-like manner) until after some time a trap falls over the cheese along with any mouse eating it. Sometimes it may be possible (or even necessary) to trigger a trap, and then quickly run in, eat the cheese and run away, before the trap falls. Other times this will not be possible, and an alternative route must be found. The concurrency required in this domain occurs between the contraptions and trap actions (these are the envelope), and the mouse's (content) actions. As an aside, it is not possible to encode this using timed initial literals since the timing of the traps falling is dependent on the actions chosen by the planner. It would seem like an ideal usage of the derived predicates also expressible in PDDL2.2. However, these are unable to handle temporal aspects and so not suitable in this case.

The Baseball Domain

This domain models an innings of baseball. The batsmen must travel around all four bases, the time taken is dependent on the speed they can run. The duration the ball is in the air is dependent both on how well the batsman can bat and how fast the pitcher is able to throw the ball. The longer the ball is in the air, the more time available for the batsmen to run around the course. Batsmen must reach a base before the ball is retrieved by the fielders. The model deliberately does not allow for one batsman to overtake another. The co-ordination in this domain is in the running of the players (some actions may happen concurrent, as with two hitters running to different bases, some must occur sequentially, where one hitter runs first to base one and then to base two) and the action that represents the ball travelling through the air.

The Café Domain

The Café domain tests both the need for required concurrency and the ability to minimise a specified plan metric. The goal is to deliver breakfast (tea, toast and a cooked breakfast) to tables in a café. However, due to the availability of only a single electrical socket in the kitchen, the toast and the tea cannot be made simultaneously. Once either is made, it starts to cool, until delivered to the table. Whilst it is preferable to have them as hot as possible when delivered, it is also preferable to deliver them at the same time (or as close to each other as possible). There are three possible metrics, one is to minimise the heat lost by each item whilst it is in the kitchen, another is to have them delivered as close as possible together (i.e. minimising the delivery window), and finally simply to minimise the total-time of the whole plan.