Dragons, Damsels and Knights

Ryan HolmesCSE 574

Dragons, Damsels and Knights

Project 1

This report describes the PDDL planning domain Dragons, Damsels and Knights (DDK) that I designed and implemented, and gives a brief analysis of several problem sets on that domain. I first describe the domain completely in written form, and then discuss the more interesting aspects. Next I describe five problems over the domain, with discussion of which aspects of the domain each problem was chosen to emphasize, and of how the FF planer solved the problems. Finally, I discuss lessons learned and ideas for extensions and improvement.

Domain Description

The DDK domain is a path-finding and conditional action planning domain. It could equally well be named terrorists, hostages and soldiers, if you were that type of person. The domain has two broad classes of objects: locations and persons, as shown in Table 1. Locations are considered to be room-like locations, and are linked with some problem-specific topology using a link predicate (See Table 2). Persons are mobile and placed within the locations using the at predicate.

Object / Description
Location / Place where a person can be at(). Linked together.
Person / Generic person, used by generic actions
Knight – Person / Subtype of person, plannable
Damsel – Person / Subtype of person, but only used as an action target
Dragon – Person / Subtype of person, plannable

Table 1: Objects in the DDK domain

Predicate / Description
Plannable(person) / Actions can be chosen with this person as the "source". No actions in the domain change this, but it allows the problem definer to choose which persons should work toward the goal state and which should not.
Alive(person) / Indicates the person is in the Alive state. This can be made false by the domain, but not true.
At(person, location) / Indicates a person is at location (room). Multiple actions can change this.
Castle(location) / Indicates the location is a castle. This can be made false by the plan, but not true.
Cave(location) / Indicates the location is a cave. No actions in the domain change this.
Link(location, location) / Indicates two locations are connected by a path. No actions in the domain change this.

Table 2: Predicates in the DDK domain

A given problem in the DDK domain specifies a world topology by specifying location objects, predicates upon them and the links between them; a world population by specifying persons and the predicates upon them; and a goal state. The plannable predicate is a precondition on every action, and every action involves a person. Therefore the problem can be modified significantly by changing which persons are plannable and thus able to "initiate" actions to affect the world.

There are eleven actions in the DDK domain, although several are given the same name with mutually exclusive preconditions. I list each action with a written description of its preconditions and effects, see the PDDL listing for the exact details.

walk(knight, location a, location b)
Requires the knight in question to be plannable and alive, at location a, and there to be a link between the locations in question in the correct direction.
Causes the knight move from location a to location b. Additionally, if an alive dragon is at location b, causes the knight to die.
escort(knight, damsel, location a, location b)
Requires the knight to be plannable, both the knight and damsel to be alive and at a, and a link between a and b
Causes the knight and damsel to move from location a to location b. Additionally, if an alive dragon is at location b, causes both knight and damsel to die.
lumber(dragon, location a, location b)
Requires the dragon to be plannable and alive, at location a, a link between a and b, and b cannot be a castle
Causes the dragon to move from a to b. Additionally, if an alive knight is at location b, causes the dragon to die.
haul(knight, person load, location a, location b)
Requires the knight to be plannable and alive, the knight and the load at a, the load to be dead, and a link between a and b
Causes the knight and the load to move from a to b. Additionally, if an alive dragon is at location b, causes knight to die.
haul(dragon, person load, location a, location b)
Requires the dragon to be plannable and alive, the dragon and the load at a, the load to be dead, b not a castle, and a link between a and b
Causes the dragon and the load to move from a to b. Additionally, if an alive knight is at location b, causes dragon to die.

taunt(knight, dragon, loc a, loc b, loc c)
Requires the knight to be plannable, alive, and at a, the dragon to be alive and at c, a link from a to b, a link from b to c, a link from c to b, b not to be a castle, a != b, b!= c, and no knight at b
Causes the dragon to move from c to b
Note: The dragon will avoid b if it is a castle, because dragons avoid castles. It will also avoid b if there is a knight (Even dead) because it might be an obvious trap. And although this action could be applied when a == c, that means the dragon and the knight are currently peacefully co-existing, which could only have happened through an initial state.
taunt(dragon, knight, loc a, loc b, loc c)
Requires the dragon to be plannable, alive, and at a, the knight to be alive and at c, a link from a to b, a link from b to c, a link from c to b, a != b, b!= c, and no dragon at b
Causes the knight to move from c to b
attack(knight, dragon, loc a, loc b)
Requires the knight to be plannable, alive, and at a, the dragon to be alive and at b, a link from a to b, and b not to be a cave
Causes the dragon not to be alive, and if any other dragon is at b, the knight not to be alive
attack(dragon, knight, loc a, loc b)
Requires the dragon to be plannable, alive, and at a, the knight to be alive and at b, a link from a to b, and b not to be a castle
Causes the knight not to be alive, and if any other knight is at b, the dragon not to be alive
attack(dragon, loc a, loc b)
Requires the dragon to be plannable, alive, and at a, a link from a to b, and b to be a castle
Causes b to not be a castle
bite(dragon, da, loc a)
Requires the dragon to be plannable and both the dragon and the damsel to be alive and at a.
Causes the damsel not to be alive

Domain Discussion

The DDK domain requires the ADL subset of PDDL to function. The primary reason for using the richer syntax is to allow secondary preconditions on the movement, causing different results depending on the contents of the target room. Although I could have eventually worked out the non-ADL versions, it was much more natural and readable using ADL.

DDK is, at heart, a path-finding and scheduling domain, similar to the DriverLog and Logistics domains. It adds complexity by allowing the mobile objects to cease to become mobile in some situations, requiring the planner to either avoid or neutralize these threats to mobility. It also places limits on mobility, in that some objects can only be moved in conjunction with other objects, or some objects cannot enter some locations without taking action to modify the situation. Because the domain is still known and deterministic it is still a very simplistic "goal-achiever", but it can give the appearance of an agent solving a complex problem.

Because multiple objects can be mobile at once, the DDK domain is well suited to parallel planning. However, I was unable to test this, because the only planner I was able to get to work (Primarily due to the ADL requirement) on DDK was FF, which does not handle multiple simultaneous actions. It did, however, interleave actions in an interesting fashion when multiple mobile objects were active (See Problem ddk-04).

Problems

I generated five problems on the DDK domain, in roughly advancing complexity. The base world arrangement for the first four is the same (See Figure 1), while the world arrangement for the final problem is slightly different (See Figure 2). I describe each in words with commentary, and then show the plan FF generated as a solution.

Figure 1: Topology layout for problems 01 through 04

Figure 2: Topology layout for problem 05

Problem ddk-01

This initial problem involves a single knight, two damsels, and no dragons. The knight begins at castle1, and must escort the damsels from castle2 and cave3 to castle1, then return to castle2. This is a simple path-finding problem, although managing the escorting of two damsels reasonably adds a wrinkle. Notice that FF handles this problem nicely, interleaving the walk/escort moves to move the two damsels efficiently to castle1.

FF plan

0: WALK KNIGHT1 CASTLE1 R1

1: WALK KNIGHT1 R1 R5

2: WALK KNIGHT1 R5 R4

3: WALK KNIGHT1 R4 CASTLE2

4: ESCORT KNIGHT1 DAMSEL1 CASTLE2 R4

5: ESCORT KNIGHT1 DAMSEL1 R4 R5

6: WALK KNIGHT1 R5 R4

7: WALK KNIGHT1 R4 CAVE2

8: WALK KNIGHT1 CAVE2 CAVE3

9: ESCORT KNIGHT1 DAMSEL2 CAVE3 CAVE

10: ESCORT KNIGHT1 DAMSEL2 CAVE2 R4

11: ESCORT KNIGHT1 DAMSEL2 R4 R5

12: ESCORT KNIGHT1 DAMSEL1 R5 R1

13: WALK KNIGHT1 R1 R5

14: ESCORT KNIGHT1 DAMSEL2 R5 R1

15: ESCORT KNIGHT1 DAMSEL1 R1 CASTLE1

16: WALK KNIGHT1 CASTLE1 R1

17: ESCORT KNIGHT1 DAMSEL2 R1 CASTLE1

18: WALK KNIGHT1 CASTLE1 R1

19: WALK KNIGHT1 R1 R5

20: WALK KNIGHT1 R5 R4

21: WALK KNIGHT1 R4 CASTLE2

Problem ddk-02

The second problem adds a dragon in cave3 and removes damsel2 from the cave. The damsel2 goal changes to moving the dragon to castle1 instead of the damsel. The knight can only do this by killing the dragon and hauling it. To kill the dragon he must taunt it out of the cave, because he cannot attack a dragon in a cave. After killing the dragon the plan is very similar to the last, except that he must interleave walk, escort and haul, instead of just walk and escort.

FF Plan

0: WALK KNIGHT1 CASTLE1 R1

1: WALK KNIGHT1 R1 R5

2: WALK KNIGHT1 R5 R4

3: TAUNT KNIGHT1 DRAGON1 R4 CAVE2 CAVE3

4: WALK KNIGHT1 R4 R5

5: TAUNT KNIGHT1 DRAGON1 R5 R4 CAVE2

6: ATTACK KNIGHT1 R5 DRAGON1 R4

7: WALK KNIGHT1 R4 CASTLE2

8: ESCORT KNIGHT1 DAMSEL1 CASTLE2 R4

9: HAUL KNIGHT1 DRAGON1 R4 R5

10: WALK KNIGHT1 R5 R4

11: ESCORT KNIGHT1 DAMSEL1 R4 R5

12: HAUL KNIGHT1 DRAGON1 R5 R1

13: WALK KNIGHT1 R1 R5

14: ESCORT KNIGHT1 DAMSEL1 R5 R1

15: HAUL KNIGHT1 DRAGON1 R1 CASTLE1

16: WALK KNIGHT1 CASTLE1 R1

17: ESCORT KNIGHT1 DAMSEL1 R1 CASTLE1

18: WALK KNIGHT1 CASTLE1 R1

19: WALK KNIGHT1 R1 R5

20: WALK KNIGHT1 R5 R4

21: WALK KNIGHT1 R4 CASTLE2

Problem ddk-03

The third problem places damsel1in cave3 and damsel2 in cave1. A single dragon is placed in cave3, while two dragons are placed on the road in front of cave1, R3. The problem goals change to simply bringing both damsels back to castle1. Both situations have different difficulties, but similar resolutions. The dragon in the cave is alone, but cannot be attacked in the cave. The dragons on the road cannot safely be attacked when they are in the same room, because the remaining dragon will kill the knight. The knight must taunt the dragons out of safety before killing each individually. Note that FF finds a very efficient plan, moving damsel2 into a good position for escorting both damsels back.

FF plan

0: WALK KNIGHT1 CASTLE1 R1

1: TAUNT KNIGHT1 DRAGON3 R1 R2 R3

2: ATTACK KNIGHT1 R1 DRAGON3 R2

3: ATTACK KNIGHT1 R2 DRAGON2 R3

4: WALK KNIGHT1 R3 CAVE1

5: ESCORT KNIGHT1 DAMSEL2 CAVE1 R3

6: ESCORT KNIGHT1 DAMSEL2 R3 R4

7: ESCORT KNIGHT1 DAMSEL2 R4 R5

8: WALK KNIGHT1 R5 R4

9: TAUNT KNIGHT1 DRAGON1 R4 CAVE2 CAVE3

10: WALK KNIGHT1 R4 R5

11: TAUNT KNIGHT1 DRAGON1 R5 R4 CAVE2

12: ATTACK KNIGHT1 R5 DRAGON1 R4

13: WALK KNIGHT1 R4 CAVE2

14: WALK KNIGHT1 CAVE2 CAVE3

15: ESCORT KNIGHT1 DAMSEL1 CAVE3 CAVE2

16: ESCORT KNIGHT1 DAMSEL1 CAVE2 R4

17: ESCORT KNIGHT1 DAMSEL1 R4 R5

18: ESCORT KNIGHT1 DAMSEL2 R5 R1

19: WALK KNIGHT1 R1 R5

20: ESCORT KNIGHT1 DAMSEL1 R5 R1

21: ESCORT KNIGHT1 DAMSEL2 R1 CASTLE1

22: WALK KNIGHT1 CASTLE1 R1

23: ESCORT KNIGHT1 DAMSEL1 R1 CASTLE1

Problem ddk-04

Problem four is a change of pace. The initial state is similar to 03, but the two dragons are moved to R5, and there is only a single damsel1, in castle2. However, the knight is no longer plannable, and all three dragons are. The goals are quantified in this problem, such that all dragons must stay alive, all knights and damsels must be dead and in cave3, and there must be no castles. FF solves this in 14 moves, interleaving actions between all three dragons and sharing the workload well. Interestingly, when I first setup this problem I did not require all dragons to stay alive, and FF took 18 moves and lost a dragon to a knight by walking into him instead of attacking. Note that this plan would be just as applicable if we didn't require all dragons to live, but adding that requirement helped FF find this shorter, more efficient plan.

FF plan

0: TAUNT DRAGON2 KNIGHT1 R5 R1 CASTLE1

1: LUMBER DRAGON3 R5 R4

2: ATTACK DRAGON3 R4 CASTLE2

3: LUMBER DRAGON3 R4 CASTLE2

4: LUMBER DRAGON1 CAVE3 CAVE2

5: BITE DRAGON3 DAMSEL1 CASTLE2

6: ATTACK DRAGON2 R5 KNIGHT1 R1

7: ATTACK DRAGON2 R1 CASTLE1

8: HAUL DRAGON2 KNIGHT1 R1 R5

9: HAUL DRAGON2 KNIGHT1 R5 R4

10: HAUL DRAGON3 DAMSEL1 CASTLE2 R4

11: HAUL DRAGON2 KNIGHT1 R4 CAVE2

12: HAUL DRAGON1 KNIGHT1 CAVE2 CAVE3

13: HAUL DRAGON3 DAMSEL1 R4 CAVE2

14: HAUL DRAGON2 DAMSEL1 CAVE2 CAVE3

Problem ddk-05

For the final problem, I experimented with a slightly deeper search path. In the 05 problem two damsels are located in cave5 and one dragon in cave4. Two knights in castle1 are plannable, and the goal is to get the two damsels back to castle1. The damsels are six moves away from the knights by either path, but going through the cave will require taunting the dragon out and killing him at R1. FF successfully takes the path of least resistance and goes around the dragon. Interestingly, only knight2 goes, and instead of the interleaved escorting we saw in the shorter path he only interleaves escorting once, then escorts damsel2 all the way back to the castle and then returns to collect damsel1.

FF plan

0: WALK KNIGHT2 CASTLE1 R1

1: WALK KNIGHT2 R1 R2

2: WALK KNIGHT2 R2 R3

3: WALK KNIGHT2 R3 R4

4: WALK KNIGHT2 R4 R5

5: WALK KNIGHT2 R5 CAVE5

6: ESCORT KNIGHT2 DAMSEL2 CAVE5 R5

7: WALK KNIGHT2 R5 CAVE5

8: ESCORT KNIGHT2 DAMSEL1 CAVE5 R5

9: ESCORT KNIGHT2 DAMSEL2 R5 R4

10: ESCORT KNIGHT2 DAMSEL2 R4 R3

11: ESCORT KNIGHT2 DAMSEL2 R3 R2

12: ESCORT KNIGHT2 DAMSEL2 R2 R1

13: ESCORT KNIGHT2 DAMSEL2 R1 CASTLE1

14: WALK KNIGHT2 CASTLE1 R1

15: WALK KNIGHT2 R1 R2

16: WALK KNIGHT2 R2 R3

17: WALK KNIGHT2 R3 R4

18: WALK KNIGHT2 R4 R5

19: ESCORT KNIGHT2 DAMSEL1 R5 R4

20: ESCORT KNIGHT2 DAMSEL1 R4 R3

21: ESCORT KNIGHT2 DAMSEL1 R3 R2

22: ESCORT KNIGHT2 DAMSEL1 R2 R1

23: ESCORT KNIGHT2 DAMSEL1 R1 CASTLE1

Limitations and Improvements

I made several trade-offs between design and implementation over the course of building the domain. Some of these were due to my original lack of familiarity with PDDL, and some were probably design flaws. I do think the domain could be made substantially more interesting with more work.

Creating sub-types of knight, dragon and damsel out of person worked well, but some of the actions had to be written twice (e.g. haul, taunt) when I wanted to make that action applicable to only two of the three types. I probably could have continued the sub-typing to create an active-person and in-active person, then made knight and dragon children of active-person. The sub-typing system allows very interesting action design ideas, and I'm glad I played with it.

I originally had castle and cave as sub-types of location, but I couldn't figure out a nice way to check if a given location was also a cave. The PDDL documentation seemed to imply that the sub-types should have become unary predicates that I could use for that test, but FF didn't seem to support that usage. So, I moved castle and cave into strict predicates. This change actually worked well, as I could then make castles destructible.

The primary limitation that I was unable to get working and would have liked to see in action was groups of persons. My original idea was that knights should have to gang up on dragons, in larger numbers than in the group of dragons they wanted to attack. This proved complex. I didn't want to define "walk-2, walk-3, …" actions that allowed more than one knight at a time, and auto-killed dragons in smaller numbers than knights on arrival. I toyed with the idea of having a meta-object of "group" that knights could get "in", but there would need to be pre-defined group-objects in the problem statement that knights (Or dragons) could join in. I think this idea could be worked with, if each knight had its own group object that others could join/leave and then would be moved with the knight. There would still be the issue of counting how many were in the group and comparing that to another group (Of dragons) though. It would be an interesting problem, and make the domain nicely richer (One could imagine knights escorting groups of damsels, requiring n dragons to attack a castle, etc.)

;; Dragons, Damsels and Knights domain

;; Ryan Holmes

;; CSE 574 Fall 2004

;; Arizona State University

;; Project 1 - September 22, 2004

(define (domain ddk)

(:requirements :strips :adl)

(:types person location - object knight dragon damsel - person)

(:predicates (at ?pers - person ?loc - location)

(link ?loc1 -location ?loc2 - location)

(alive ?pers - person)

(plannable ?pers - person)

(castle ?loc - location)

(cave ?loc - location)

)

;; Only knights can walk. They shouldn't walk into dragons though.

(:action walk

:parameters

(?k - knight

?loc-from - location

?loc-to - location

)

:precondition

(and (plannable ?k) (alive ?k) (at ?k ?loc-from) (link ?loc-from ?loc-to)

)

:effect

(and (not (at ?k ?loc-from))

(at ?k ?loc-to)

(forall (?x - dragon)

(when (and (alive ?x) (at ?x ?loc-to))

(not (alive ?k))

)

;; Knights can attack dragons, but not in caves. They also shouldn't attack when outnumbered.

(:action attack

:parameters

(?k - knight

?loc-from - location

?d - dragon

?loc-to - location

)

:precondition

(and (plannable ?k) (alive ?k) (at ?k ?loc-from)

(alive ?d) (at ?d ?loc-to)

(link ?loc-from ?loc-to) (not (cave ?loc-to))

)

:effect

(and (not (at ?k ?loc-from))

(at ?k ?loc-to)

(not (alive ?d))

(forall (?x - dragon)

(when (and (not (= ?x ?d)) (alive ?x) (at ?x ?loc-to))

(not (alive ?k))

)

;; Only knights can escort. They should avoid feeding dragons.

(:action escort

:parameters

(?k - knight

?d - damsel

?loc-from - location

?loc-to - location

)

:precondition

(and (plannable ?k) (at ?k ?loc-from) (at ?d ?loc-from) (alive ?k) (alive ?d) (link ?loc-from ?loc-to)

)

:effect

(and (not (at ?k ?loc-from)) (at ?k ?loc-to)

(not (at ?d ?loc-from)) (at ?d ?loc-to)

(forall (?x - dragon)

(when (and (alive ?x) (at ?x ?loc-to))

(and (not (alive ?k))

(not (alive ?d))

)

;; Knights can haul dead persons.

(:action haul

:parameters

(?p - knight

?load - person

?loc-from - location

?loc-to - location

)

:precondition

(and (plannable ?p) (alive ?p) (not (alive ?load))

(at ?p ?loc-from) (at ?load ?loc-from) (link ?loc-from ?loc-to)

)

:effect

(and (not (at ?p ?loc-from)) (at ?p ?loc-to)

(not (at ?load ?loc-from)) (at ?load ?loc-to)

(forall (?x - dragon)

(when (and (alive ?x) (at ?x ?loc-to))

(not (alive ?p))

)

;; So can dragons.

(:action haul

:parameters

(?p - dragon

?load - person

?loc-from - location

?loc-to - location

)

:precondition