Contents

Making Them Think

Predefined Behavior

Goal-Directed Behavior

The Middle Ground

A Simple Tutorial: Maze Solving

Discussion

Notes and References

A Simple Tutorial Example: Maze Solving

We already looked at some predefined behavior for solving a maze. Let's take a look at a goal-directed approach to the problem. Of course, since there are well-known predefined behaviors for maze solving, we would not suggest using a goal-directed approach in a real application. Therefore, this section is simply meant as a tutorial example to show how some of the different pieces fit together.

Domain Knowledge

Let us suppose we have a maze defined by a predicate Free(c), that holds when, and only when, the grid cell c is "free". That is, it is within range and is not occupied by an obstacle.

Occupied(c), sizex, and sizey each depend upon the maze in question. In addition, there are two maze dependent constants start and exit that specify the entry and exit points of a maze. Figure 9 shows a simple maze and the corresponding definition.

Figure 9. A simple maze.

We also need to define some functions that describe a path within the maze. We say that the adjacent cell "North" of a given cell is the one directly above it, similarly for "South", "East", and "West".

There are two fluents; position denotes which cell contains the character in the current situation, and visited denotes the cells the character has previously visited.

The single action in this example is a move action that takes one of four compass directions as a parameter. It is possible to move in some direction d, provided the cell to which we are moving is free and has not been visited before.

Figure 10 shows the possible directions a character can move when in two different situations.

Figure 10. Possible directions to move

A fluent is completely specified by its initial value and its successor-state axiom. For example, the initial position is given as the start point of the maze and the effect of moving to a new cell is to update the position accordingly.

So for example, in Figure 9, if the character has previously been to the locations marked with the filled dots, and in situation the character moves north to the unfilled dot, then we have that position(s) = (2,0) and that position(do(move(north),s)=(2,1).

The list of cells visited so far is given by the defined fluent . It is defined recursively on the situation to be the list of all the positions in previous situations (we use standard Prolog list notation).

For example, in Figure 9, when

we have that (s) = (2,1), and that (s) = .

Character Instruction

We have now completed telling the character everything it needs to know about the concept of a maze. Now we need to move on and use complex actions to tell it about its goal and any heuristics that might help it achieve those goals. As a first pass, let's not give it any heuristics, but simply provide a goal-directed specification of maze-solving behavior. Using complex actions we can express this behavior elegantly as follows:

Just like a regular "while" loop, the above program expands out into a sequence of actions. Unlike a regular "while" loop, it expands out, not into one particular sequence of actions, but into all possible sequences of actions. The precondition axioms that we previously stated, and the exit condition of the loop, define a possible sequence of actions. Therefore, any free path through the maze, which does not backtrack and ends at the exit position, meets the behavior specification.

Note that the use of regular programming constructs may initially cause confusion to the reader of the above code. Most of the work is being done by the nondeterministic choice of arguments operator "". The example makes it clear that by "nondeterministic" we do not mean that anything random is happening; we simply mean that we can specify a large number of possibilities all at once. In particular, the (d) construct should be read as "pick the correct direction d". For the mathematically inclined, perusing the definitions may serve to alleviate any sense of bewilderment. To make things even clearer we shall, however, consider the expansion of the complex actions in terms of their definitions. The expansion is based on the simple maze described previously in Figure 9.

In the initial situation we have . Thus the guard of the "while" loop holds and we can try to expand

Expanding this out into the full definition gives

However, from the action preconditions for and the definition of the maze we can see that:

This leaves us with s = do(move(north), s0) V s = do(move(east), s0).That is, there are two possible resulting situations. That is why we refer to this style of program as nondeterministic.

In contrast, in situation s = do(move(north),s0) there is only one possible resulting situation. We have Do((d) move(d),s,s') that expands out into s'=do(move(north),s).

If we expand out the macro

from start to finish, we get

So, as depicted in Figure 11, our "program" does indeed specify all paths through the maze.

Figure 11. Valid Behaviors

Although we disallow backtracking in the final path through the maze, the character may use backtracking when it is reasoning about valid paths. In most of the mazes we tried, the character can reason using a depth-first search to find a path through a given maze quickly. For example, Figure 12 shows a path through a reasonably complicated maze that was found in a few seconds.

Figure 12. Maze solving in practice

To speed things up, we can start to reduce some of the nondeterminism by giving the character some heuristic knowledge. For example, we can use complex actions to specify a "best-first" search strategy. In this approach, we will not leave it up to the character to decide how to search the possible paths, but constrain it to first investigate paths that head toward the exit. This requires extra lines of code, but could result in faster execution.

For example, suppose we add an action goodMove(d), such that it is possible to move in a direction d if it is possible to "move" to the cell in that direction and the cell is closer to the goal than we are now.

Now we can rewrite our high-level controller as one that prefers to move toward the exit position whenever possible.>

At the extreme, there is nothing to prevent us from coding in a simple deterministic strategy such as the "left-hand" rule. For example, if we introduce a defined fluent dir that keeps track of the direction the character is traveling, and a function ccw that returns the compass direction counterclockwise to its argument, then the following complex action implements the left-hand rule.

The important point is that using complex actions does not rule out any of the algorithms one might consider when writing the same program in a regular programming language. Rather, it opens up new possibilities for high-level specifications of behavior at a cognitive level of abstraction.

_______________________________________________________________

Discussion