Project 1: Regular Languages and Pursuit-Evasion

CSCI 561 Submission Period: August 24-31, 2017

Pursuit-evasion games are scenarios with multiple agents where one agent attempts to avoid capture by another. Consider a variation of pursuit-evasion games as follows:

Two agents share a grid environment: a human (evader) and wumpus (pursuer).

The human and wumpus alternate moves on the grid. The wumpus moves each turn up,

down, left or right. The human can move up, down, left, right, or remain in place.

If the wumpus and human ever occupy the same grid cell, the wumpus eats the human.

If the human reaches a designed grid cell, they escape.

Answer the following questions using your implementation of finite automata operations for sup- port.

For the map in Figure 1, construct a discrete event system model. Assume that the humans movements are controllable and that the wumpuss movements are not controllable.

For your DES model of Figure 1, construct a specification for the human to avoid the wumpus and escape.

(a) Can the human avoid being eaten? Prove yes or no via automata operations. (b) Can the human escape in finite time (fixed number of steps)? Prove yes or no.

Design a map where the wumpus can always eat the human and prove via a DES model that this is the case.

Design a map where the human can always escape and prove via a DES model that this is the case.

W | | E

| O |

H | |

Figure 1: Example wumpus-world map. W represents the initial location of the wumpus. H represents the initial location of the human. E represents the escape location. O represents an obstacle that neither the human nor wumpus can move into.