• The Rover - each Rover is a robot and connects to the stage program at a separate port. A Rover can be in one of several states, depending on which role it is given by the Prodigy. Rovers do not know their own pose; the poses are stored on the Prodigy due to their volatile state.
• The Prodigy - a singleton object that coordinates the Rovers and handles the mapping. When a Rover takes laser readings and converts them into world coordinates, they report this to the Prodigy which records the data. The relationship between the Prodigy and the Rovers is completely method invocation, to show that the system can be ported to use RMI over a wireless LAN, etc. Moreover, I use Monitor Object thread synchronization pattern to avoid race conditions in the multi-threaded environment.
• The Record - a small container on the Prodigy side to encapsulate Pose and role-oriented data for each Rover.
• The Shell - I implemented a small shell so I could type commands at it during the program run. Typing "bye" performs an immediate shutdown and map export.

• Laser range finders to cover the front 180 degrees, with a maximum range of 8000.
• PTZ vision camera
• BlobFinder interface
• Fiduciary interface

There are two main robot roles: Scout and Observe. The roles are disseminated by the Prodigy, and each new cycle of the Rovers' life cycles checks to see which role they play and branch accordingly. In addition to the single role, their are quite a few boolean and integer data types in the class to get more specific, appropriate behavior across cycles. In order to better explain the roles and their interaction, I will do a brief walkthrough of a possible mapping scenario.

The Init Phase

The Prodigy and Shell initialize - the Prodigy allocates all memory for the boolean[][] map and spawns two Records, each with a target Rover.

First, neither Rover has a role - they are considered Free, or for lack of a better word, asleep. The Prodigy chooses one of the two free Rovers to become an Observer. The Observer immediately rotates around until it picks up the other (sleeping) Rover on its laser & fiduciary sensors. Once it spots the Rover, it tells the Prodigy that it's own coordinates are (0,0) and it's heading is 0. The Prodigy tells the other robot to don the Scout role. This concludes the starting phase. In extremely simple pseudo-code across all modules:

while (true) {
   if (Observer.foundScout()) {
      Prodigy.initiateCoordinates()
      Other_Robot.becomeScout()
      break;
   }
   else {
      Observer.keepRotating();
   }
}

The Mapping Phase

We have one Observer and one Scout. The Scout is to orient itself to a target heading (which is set to 0 initially) and start trucking. If it encounters a wall, it uses a simple wall-walking algorithm (trying to maintain a set distance from the wall) until it gets around it and finds its desired heading again. It will continue to do this until it gets a Backup signal from the Prodigy (discussed below).

Every N (currently 50) cycles it stops, gets its pose from the prodigy, and uses its laser data to read its surroundings. Using trig and java.Math library, the Rover will convert the laser ray into world coordinates and report the data to the Prodigy for filing. The Prodigy then iterates over all active rovers and makes sure that the laser data isn't identifying another robot. If not, it marks it in the boolean[][] map.

The Observer's role is simply to look at its sensor data and rapidly update the Prodigy with the pose (heading & location) of the observed Scout. Of course, the Observer cannot move because that would nullify all further observations. If the Observer loses track of the Scout (that is, it is behind an obstacle, too far away, not within the front 180 degrees of the Observer, or any combination of the three), the Observer sends a signal to the Prodigy that the Scout is out of range. In extremely simple pseudo-code across all modules:

while (true) {
   if (Observer.lostScout()) {
      Prodigy.reunite();
      break;
   }
   else {
      Observer.updateScoutPosition();
      Scout.walkAbout()
      Scout.doMapping()
   }
}

The Reunite Phase

This is where the Prodigy sends the Backup signal to the Scout. The Scout immediately backs up until it is once again within plain view of the Observer. The Observer acknowledges the Backup action and sends a SwitchOff signal to the Prodigy. The idea now is to switch roles and make the former Scout watch as the former Observer rushes to reunite.

I order to do this gracefully, the Prodigy tells the current Scout to become an Observer. Just as in the Init Phase, the new Observer (we'll call him Observer') will orient himself to look at the former Observer and send the signal to the Prodigy to turn him into a new Scout, or Scout'. The Prodigy does this, but sends a CatchUp signal to the Scout' so that instead of Scout' orienting himself in a new direction and wandering around, he orients himself toward Observer'. He makes his way over, careful not to hit any obstacles. Once within a certain distance, we switch back. In extremely relaxed pseudocode across all modules:

while (Observer.cannotSeeScout()) {
   Scout.backUp();
}
Observer' = Scout;
Observer'.becomeObserver();
Observer'.faceTarget();
Scout' = Observer;
Scout'.catchUp();

while (!Scout'.caughtUp()) {
   Observer'.updateScoutPosition();
   Scout'.faceObserver();
   Scout'.goForward();
}
Observer = Scout';
Observer.becomeObserver();
Scout = Observer';
ReturnToMappingPhase();


Progress Towards a Complete Map

As I learned in CS550, a random walk doesn't guarantee a complete or even representative mapping of an area within a bounded time. Random walk was great for testing when it came to the first and second deliverables, but it makes sense to come up with a better strategy for covering ground. My two-robot mapping strategy, as discussed above, lets the Scout lead the way.

The Scout's walking strategy is more complicated than a random walk. Before stepping forward in any direction, the Scout first faces the target heading. If it encounters an obstacle, it will walk the wall until it regains its initial heading. At that point, it continues until the next obstacle. If the Prodigy then switches the target heading, we can control where the Scout walks and thereby control which pieces of the map we record.

Instituting this gives expected behavior at right. If the wall-walking and obstacle avoidance works correctly and we progress in each direction sufficiently, we will expand our occupancy grid to the extremities of the world.

The Shutdown Phase

The mapping procedure will safely terminate from the Prodigy side if one of the three following occur:

1. The uncovered map has reached a significant [expected] size in terms of the min/max x/y we've seen.
2. The user has aborted via the Shell command 'bye'.
3. We have taken an immediately large number of readings - this is to ensure that the program terminates eventually on its own.

In a safe termination, I give all Rovers the shutdown command, and they immediately exit their lifeCycle loop. I use the .class file provided in CS550 to convert a two-dimensional array to a .pnm.gz file. The output is Scott.pnm.gz, ready to be viewed with a graphics viewer.

Hybrids are actually more like Observers than Scouts. That is, they share the same Role as Observers, but in addition they consistently center their view around their target Rover and maintain that they are within a reasonable distance of the target Rover by stepping forward each time. This ensures that we attain a larger distance before we have to turn around and let somebody (most often the final observer) catch up. Moreover, we can bend the chain around corners so that the scout can take more radical turns without the final observer having to catch up every time.

Robots can identify one another through a fiduciary ID tag, which allows them to differentiate among multiple robots in range and follow the correct Rover.

An interesting property of this approach that I had not realized until I began implementation is that a single observer can safely observe a handful of hybrid/scout successors. With this chain-of-command approach, a Rover's pose is correct its observer's pose is correct. So...

for Rovers A->B->C->D->...
(where -> == observes and A is the end Observer)...

Pose correctness is associative such that:
Pose(D) depends on C. Pose(C) depends on B.
Therefore, Pose(D) depends on B.

Due to the associativity, we can simply observe an indirectly dependent Rover from a rover upwards on the chain of command. This allows for an interesting method of failure handling for anywhere in the chain of Rovers:

• If we experience a failure at the bottom of the chain (Scout-side), we simply elect the Scout's direct observer to be the new Scout.
• If we experience a failure at the top of the chain (static Observer-side), we can make the topmost hybrid the new static Observer.
• If any Rover C fails (or gets stuck against a wall in my experience) somewhere in the middle of a chain, we can easily have some Observer B->C adopt any or all of its observed Rovers (D->...) if they are in sight. In this case, the train would continue with the mended link. If B cannot see any of {D->...}, B will become a Scout and proceed with mapping until it finds them. If D is the Scout, it is has then become abandoned. It will stop where it is, assuming it knows its pose at that instant, and it will become a static observer. This means that it can still update other Rovers' poses if they are in sight.