This application, over three exercises, implements a simple version of the Shakey robot system, using the simple Deductive Data Retriever.

Shakey was one of the first intelligent robots in AI. Many people worked on many aspects of the system, from computer vision to motion, but the part relevant here is Cordell Green's application of logic programming to the planning problem, details of which can be found in "Application of Theorem Proving to Problem Solving." That paper does the Monkey and Bananas problem, Towers of Hanoi, and robot planning.

These exercises require the following files from the C25 library:

• ddr.lisp -- the code for the Deductive Data Retriever
• shakey-tests.lisp -- the test cases for these exercises

shakey-tests.lisp defines all the tests in the package named shakey-tests. The easiest way to work on these exercises is to write all your code in the shakey-tests package, that is, create a file and start the file with (in-package #:shakey-tests).

Feel free to create new test cases!.

Exercise: Shakey 1.0

Global variable name: *shakey-1-kb*

Tests: shakey-1 in shakey-tests.lisp

A common problem in early robotic planning was moving boxes from one room to another, given information about box locations (current and desired), room locations, doors being open or closed, etc. Several kinds of information need to be represented:

• Unchanging facts, such as how rooms are connected: these can be represented as static facts in the knowledge base
• Facts the robot can change, such as where it is: these can be represented in a state structure, as with Monkey and Bananas
• The problem to be solved: this can be represented by describing an initial state and a desired goal state

For Shakey 1.0, create a set of facts and rules to allow the Retriever to solve simple Shakey problems. Follow the model of the Monkey and Bananas example in monkey-general.lisp. This is similar to the version in ddr-tests, but using a more general set of rules. The rules are described in comments at the start of monkey-general.lisp.

Assume that Shakey only has to move 1 box from 1 room to another, and there are no locked doors. The term for representing a state is simply (v1-state robot-location box-location). The v1- indicates this is for version 1.0.

There are just two actions that change state:

• (MOVE-TO location): the robot moves to a location, where a location can either be the hall or a room
• (PUSH-BOX location1 location2): the robot pushes a box from one location to another.

To keep things simple, ignore the subproblem of finding paths from rooms to rooms. Instead, assume that all rooms are connected to the hall, so the rules for moving and pushing boxes from one room to another are simply:

• First move or push the box from the first room to the hall
• Then move or push the box to the second room

Use the same PLAN-FOR framework used in the Monkey and Bananas code in ddr-tests.lisp. You should only need to define:

• rules for RESULT for what happens to states when you move and push boxes
• rules for ACTION-FOR for choosing an action, given a current state and a goal state

The ACTION-FOR rules are where you make the robot smart enough to avoid getting into endless loops.

Tip: use all-different to quickly say that room1, room2 and room3 are all different.

Exercise: Shakey 2.0

Global variable name: *shakey-2-kb*

Tests: shakey-2 in shakey-tests.lisp

This is the hardest of the three Shakey exercises. When Shakey 1.0 is working, extend it to handle locked rooms. The robot should be able to unlock a room from the hallway, but not from inside the room. A robot can only enter or leave a room, when moving or pushing a box, if it's unlocked.

The easiest way to do this is by extending the state to include a list of the unlocked rooms. Make a new version of Shakey 1.0, where:

• the rules use the state form (v2-state robot-location box-location unlocked-room-list)
• the rules for selecting MOVE-TO and PUSH-BOX require the rooms involved to be unlocked
• rules are added for the action UNLOCK which lets a robot in the hall unlock any room, i.e., add it the list of unlocked rooms

The test cases start with easy cases, where the room the robot needs to enter, is in the unlocked list. The later cases start with an empy list of unlocked rooms.

Tip: use member to determine if a room is unlocked, i.e., in the list of unlocked rooms.

Exercise: Shakey 3.0

Global variable name: *shakey-3-kb*

Tests: shakey-3 in shakey-tests.lisp

When Shakey 2.0 is working, extend it to handle multiple boxes. We will assume that there's at most one box in a room, so all we need to do is give a list of the rooms that have a box in them. Shakey's goal is to move all such boxes into a destination room.

There's not a lot of additional rules needed to do this. Most of the work will still be done by the Shakey 2.0 rules. The trick is to create a new state that contains:

• the robot's initial location
• a list of the rooms with boxes to move,
• a goal room, into which boxes need to be moved, and
• a list of the locked rooms, as with Shakey 2.0

Capture this with the state form (v3-state robot-location box-room-list goal-room unlocked-room-list)

The robot is done when box-room-list is empty. If the list isn't empty, the robot should

• find a plan for getting the first box in the list to the goal room, using your Shakey 2.0 rules,
• find a plan for the remaining rooms
• return the combined plan.

To combine plans, use the deductive rules for APPEND shown in ddr-tests.lisp.

Only submit the additional rules.

Comments? Send mail to Chris Riesbeck.