Campus Tour Guide Robot

Project #2

Topological Map Algorithms

Still Under Construction

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.

Robi logical sensors:

topStruc: What is the topological structure of this place?

curLoc: What is the identifier of the current location?

Robi behaviors:

senseLoc: Read location sensor

senseEnv: Read environs sensor

turn: Rotate in place a designated number of intersection outpaths.

travel: Go to next point along outpath.

map: An internal behavior (not sent to simulator)

Simulator data & data structures:

robiLoc: current location of robot

robiDir: node toward which robot is heading

AdjList: Adjacency list of RobiWorld, which is stored as a structure containing:

          numPaths

          array of names of neighbors

Simulator action:

Responses to robot’s execution of behaviors:

senseLoc: Return robiLoc; 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:

myLoc: robot’s information about its location

fromLoc: robot’s previous location

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

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

worldMap: Adjacency list being built up by robot

Robi control actions:

mainControl:

toDir ← 0

fromLoc ← “?”

myLoc ← senseLoc

numPaths ← senseEnv

makeNewNode(myLoc, numPaths)

map

end

travel:

fromLoc ← myLoc

myLoc ← senseLoc

numPaths ← senseEnv

If newLoc(myLoc) then

          newL ← true

          makeNewNode(myLoc, numPaths)

          fromLoc.neighbor(toDir) ← myLoc

          myLoc.neighbor(0) ← fromLoc

          toDir ← 1

Else

          newL ← false

          If initLoop then

                   initLoop ← false

                   fromLoc.neighbor(toDir) ← myLoc

                   myLoc.neighbor(numPaths-1) ← fromLoc

          Else

          End If

          xxx

          yyy

          zzz

End If

turn(n):

toDir ← (toDir + n) mod numPaths

map: See below

map:

done ← false

initLoop ← true

travel

while not(done) do:

          while newL do:

                   travel

Robi internal actions:

makeNewNode(nowLoc, numPaths):

Create new data structure with the following:

.name ← nowLoc

.numPaths ← numPaths

Create array, neighbor, of numPaths elements with the following

for (i::0 ? numPaths) neighbor(i) ← “?”

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.