Rossum -> Papers and RFC's -> AutoPilot Paper
Link to The Rossum Project Home Page 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 Strategy

Before 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?

Floor Plan Showing Navigation Network

Picking the Best 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.

Improved Realism

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.

Copyright (C) 2000 by G.W. Lucas.
All rights reserved except as otherwise marked.

Trinity Fire-Fightning Home Robot Contest Design Copyright (C) 2000 by Trinity College.
Used with permission.