Campus Tour Guide Robot

Project #2

Topological Map Algorithm

CIS480

First let’s establish what information the robot needs in order to function.  Then we determine how the simulator keeps track of that information and what functions the robot can call in order to receive that information from the simulator.  Those functions are, in essence, logical sensors provided to the robot by the simulator.  These, in conjunction with the simulator data structures determine the simulator algorithm.

Next we establish the functionality of the robot, in essence, generating its set of  behaviors.  These, then, must be implemented as the robot’s algorithm.

The algorithmic description below is based on a functioning program.

Robi logical sensors:

senseLoc: What is the identifier of the current location?

sensePaths: How many paths emanating from this intersection?

Robi behaviors:

senseLoc: Read location sensor

sensePaths: Read environs sensor

turn(numTicks): Rotate in place numTicks locations.

travel: Go to next point along outpath.

map: An internal behavior (not sent to simulator)

Simulator data & data structures (simData):

robiLoc: current location of robot

robiDir: outpath # indicating direction toward which robot is heading

simMap: Set of nodes (structures) containing:

          locId

numPaths

          set of neighbors (by id or #)

Simulator action:

Responses to robot’s execution of behaviors:

senseLoc: Return robiLoc Id; no change to simData.

senseEnv: Return number of outpaths at current location; no change to simData.

turn(n): robiDir ← (robiDir + n) mod number of outpaths; return nothing.

travel: prevRobiLoc ← robiLoc

robiLoc ← robiLoc.neighbor(robiDir)

from-index ← index-of(prevRobiLoc) {with respect to robiLoc.neighbor array}

robiDir ← (from-index + 1) mod robiLoc.numPaths

Robi data & data structures:

myLocName: Id of robot’s location as kept by robot

myLoc: robot’s information about its location

prevLoc: robot’s previous location (as kept by robot)

myDir: robot’s heading, as index into neighbor array

goalDir: direction robot wants to head

numPaths: how many outpaths (neighbors) are at this location

robiMap: Robot’s set of nodes (structures) containing:

          locId

          mapped – Boolean variable indicating mapping status

numPaths

          set of neighbors (by #)

Robi control actions:

map:

myLocName ← senseLoc

numPaths ← sensePaths

myDir ← 0

goalDir ← 0

myLoc ← makeNewNode(myLocName, numPaths)

travel

doneMapping ← False

While Not doneMapping

        prevLoc ← myLoc

        myLocName ← senseLoc

        numPaths ← sensePaths

        If prevSeen(myLocName) Then

                myLoc ← getLoc(myLocName)

                fromDir ← getFromDir(myLoc, prevLoc)

        Else

                myLoc ← makeNewNode(myLocName, numPaths)

                fromDir ← 0

        End If

        myDir ← (fromDir + 1) Mod numPaths

        robiMap(prevLoc).neighbor(goalDir) ← myLoc

        robiMap(prevLoc).mapped ← isMapped(prevLoc)

        If Not robiMap(myLoc).mapped Then

                robiMap(myLoc).neighbor(fromDir) ← prevLoc

                robiMap(myLoc).mapped ← isMapped(myLoc)

        End If

        If robiMap(myLoc).mapped Then

                doneMapping ← gotoClosestInc(myLoc, myDir)

        End If

        If Not doneMapping Then

                goalDir ← chooseDir(myLoc)

                turn ((goalDir + numP - myDir) Mod numP)

                travel

        End If

Wend

makeNewNode(locName, numPaths):

Create new node & store initial info

prevSeen(locName):

Boolean – has robot been to this location previously

getLoc(locName):

Look up the Id# corresponding to this location’s name

getFromDir(thisLoc, prevLoc):

Look up the path # corresponding to the direction from which robot came

isMapped(loc):

Boolean – has indicated location been mapped

gotoClosestInc(thisLoc, direction):

Starting from current location and direction robot is facing:

        Find the closest unexplored (incomplete) node, if there is one

                Generate a path to it

                Go to that node

                Return False

        But, if no path is found, Return True

chooseDir(thisLoc):

Choose the next direction for robot to travel in accordance with this:

        First – assumption is that the location has not been fully mapped

        Second – starting with direction #0, return the first unmapped direction

found.

errorReport(. . info parameters . . ):

This is designed to be called from places in the program which expect to encounter certain values within specified ranges. 

If that fails to occur call this function sending it information helpful for debugging. 

Write that information to the Debug file.

Halt execution.

Comments:

Notice that we have a very stylized robot+simulator.  Nevertheless this structural template can be modified step by step to make an ever more realistic R+S, even to the point of introducing random and intermittent sensor error and moderately faulty actuator performance.  The key is to decompose the robot functions into sensors and actuators and to provide a simulator capable of supplying the designed functionality.  A second essential of implementation is – following the principle of agile programming – to create a working R+S pair at every step of the way.