|Rossum||Papers and RFC's||AutoPilot Paper|
|Simulator | FAQ | Downloads|
|The AutoPilot Demo|
|In the AutoPilot application, the Rossum Project's RP1 simulator shows a virtual robot navigating the floor plan for the Trinity College Fire-Fighting Home Robot Contest. Looking at the display, you'll notice that the floor is marked by a network of "roads and intersections." This network provides the simulated robot with a digital map of the contest arena. The AutoPilot software uses the map to compute a strategy for searching for its target (a lighted candle).|
Search StrategyBefore the robot can begin its search, it needs to answer an important question: where should it look first?
The mock house used in the Trinity Contest consists of four rooms. One of them is selected at random as the location of the candle. The robot can search the rooms in any sequence it chooses. Which is best? Because there are 4 rooms, there are 24 different sequences in which they may be searched (the number of permutations of 4 objects is equal to 4x3x2x1, or 24). The AutoPilot program examines its navigation network, computes the time required for each sequence, and uses that information to chose an optimal search plan.
Which room would you search first? One choice is the sequence that can be completed most quickly (considering distance, turn rates, and acceleration). For this simulation, that's CBAD. Is that the one you would choose for your search plan?
It turns out that the quickest sequence is not always the best search plan.
Why not? Because the robot does not always complete a sequence.
If the candle is in the first room it searches, the robot can extinguish
the flame and head home without searching the other rooms in the sequence.
Since it often doesn't have to complete the last legs of the search,
it makes sense to delay the most time-consuming transits to the end of
the search. To pick a good search plan, the AutoPilot software weights the
travel time required for making the transit to each room by the probability
that it actually needs to go there. No matter where the candle is placed,
the robot always searches the first room. In 1 out of 4 cases, it finds the
candle in the first room and does not travel to the second. In half of all
cases, it will not reach the third room. And in 3 out of 4 cases, it will
not search the last.
So the AutoPilot software rates each search sequence according to the score function shown below. For each permutation of the four rooms giving some sequence (a, b, c, d), we have:
|Ta is the time required to transit to room a (the first room in the permuted sequence).|
|Ti,j is the time required to transit from room i to room j (Ta,b is the time required to travel from room a to room b).|
Which room does the AutoPilot choose? The current implementation
thinks that DABC is the preferred search plan, though the best few
sequences all score very close to each other. Keep in mind that
this optimization is driven by the geometry and performance of one
particular platform... your mileage may vary.
Of course, the current version of the AutoPilot demo is not very realistic. For example, it assumes that the robot executes it search by performing a series of point-and-shoot maneuvers: It stops, pivots to face its next goal, and then travels forward in a straight line.
If you watch the most successful competitors in the Fire-Fighting Contest, you'll notice that they seldom make point-and-shoot maneuvers. Instead, they try to maintain a steady speed making wide turns around corners just as you would if you were driving a remote-control car. Future versions of AutoPilot will attempt to follow a search plan which conserves momentum as much as possible (not only do changes in speed waste time and battery power, they also increase errors in dead reckoning calculations).
AutoPilot also depends on perfect navigation, something that does not happen in real life. The simulated robot always knows exactly where it is and how it is positioned. In real robots, slop in gear systems, imperfect motor control, and occasional losses of traction can introduce significant errors into dead reckoning calculations.
The more sophisticated competitors in the Fire-Fighting Robot Contest
depend on infrared or ultrasonic range and proximity sensors to sense walls
and help them maintain their course. Although such sensors are available
in the RP1 simulator, AutoPilot does not take advantage of that feature.
Proximity sensors will be used in future implementations.
One idea that the RP1 documentation always tries to get across is this: working with a simulator is interesting only to the degree that it assists in the creation of real robots. Ultimately, the software (or, at least, the algorithms) developed for the AutoPilot demo is intended to move into a real platform.