Functional Description

We propose to design a CMOS chip that will simulate navigation through an unexplored maze. This functional specification will address the following topics: what the robot does, the state machine, I/O behavior, the robot's search algorithm, the ALU, register requirements.

Overview

The implemented algorithm will navigate an unknown maze, represented by a 4x4 grid. Included in the maze are a starting point, a goal, and various obstacles. Movement through the maze is confined to moving from the present location to any adjacent location. Two or more state machines (including the primary FSM) control the decision making process. Control lines allow interface with the chip for debugging purposes, as well as uploading and downloading data.

State Machine

A state machine will be designed to serve as the primary control. This FSM will incorporate modes for I/O communications, search algorithm stepping, and diagnostics. We anticipate using a large number of states and therefore, might need a five bit register to keep track of the various states. In addition, several smaller state machines will be used to aid the primary FSM in the implementation of the algorithm.

I/O Behavior

Inputs include multiplexed control lines to load and dump data, as well as to interrogate the ALU and buses for diagnostic purposes. There are also three uni-directional three-bit buses. Outputs include run-time status bits.

Search Algorithm

The search algorithm is composed of a deterministic, trial-and-error based protocol. The maze consists of 16 cells, which contain two bits of state data: unexplored, empty, and obstacle. Progress towards the goal will be made via empty or unexplored cells. Cells that do not lead to the goal (determined by the algorithm) are labeled obstacles and cannot be explored again. As exploration proceeds, more and more cells become dead ends. The algorithm itself is very simplistic, using an internal map matrix to keep track of its interaction with the world.

ALU

The chip will require a simple ALU with 3 bit increment, decrement, and compare. Since all operations are 3-bit operations, and since there are only three possible operations, the ALU is implemented using a PLA. This decision was made because an ALU composed of discrete components would take up too much room on chip. There may be specialized compare functions for scanning rows and columns in the map matrix.

Register Requirements

As stated previously, the chip will require 2 matrices, a maze matrix and a key matrix. The key matrix will be loaded at run time. Both matrices are 4x4 cells, but the key matrix has 2 bit cells while the maze matrix contains 1 bit cells. Known registers include Starting Position (6 bits), Goal (6 bits), Current Position (6 bits), Direction (2 bits), and Control State (5 bits).

To return click here.

Please send comments to jpfrantz@rice.edu.