These three exercises implement a simple version of the Shakey robot system, using the 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:

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!.

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:

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:

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:

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

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.

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 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.

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:

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

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

Only submit the additional rules.

A Universal Planner

Implement simple universal planning rules. Test that they can solve the test cases for Blocks World Stacking and the Monkey and Bananas.

Hint: Don't reinvent MEMBER. Do that exercise first and use those rules.

Faculty: Chris Riesbeck
Time: Monday, Wednesday, Friday: 1pm - 2pm
Location:Annenberg G15


Important Links