Where am I? Autonomous exploration with a TurtleBot

The TurtleBot localising and navigating in the contest environment, with the map building in RViz alongside.

Contest reports (PDF) Code Watch it map

6×6m

Unknown room

Static obstacles, no prior map

57°

Kinect field of view

One horizontal slice, 1-D from a 2-D image

3

Bumpers

180° of contact sensing at base level

3

Strategies

And a state machine to pick between them

100s

Stall detector

No new area, and frontier takes over

5×

Frontier's margin

Over a naive nearest-frontier bug

Watch the map appear

The robot below has the same sensors and the same four controllers: a 57° range scan, an occupancy grid updated by ray casting, and a differential base at 0.25 m/s. Cream is floor it has confirmed, red is obstacle it has seen, and dark grey is everything it still does not know. Pick a strategy and watch the grey get eaten.

The room

Strategy

Room 3 Obstacles 7

Speed 8× Show me the room it cannot see

Green is where it has been; the yellow wedge is what the Kinect can see right now. When frontier exploration is driving, the dashed yellow line is the path it planned to the nearest unmapped boundary.

Race them

All four strategies, same room, 300 seconds each

The contest's actual question. Run it on whatever room you have set above — the seed and the obstacle count both change the answer, which is the point.

Press the button.

Three controllers and a state machine

The classic taxonomy splits robot control three ways, and the contest controller uses all three because each fails somewhere the others do not.

Reactive control maps sensor straight to actuator with no state: a bumper closes, the wheels reverse. It is the fastest possible response and it is the only thing that can be trusted to prevent damage, so it sits at the bottom and can pre-empt everything above it.

Behaviour control keeps a little state and pursues a short-horizon goal — follow this wall, back away from that obstacle, turn towards open space. It is what the robot does most of the time.

Deliberate control builds a model and plans over it. Frontier exploration is the deliberate layer: take the occupancy grid, find the boundary between known-free and unknown, plan a path there, follow it. It is the only one of the three that can decide to cross the room.

The insight the contest forces on you is that the deliberate layer is not simply better. Frontier exploration needs a map to plan over, and at the start there is no map. Running it from the first second means planning to a frontier that is a metre away, arriving, and re-planning to one a metre beyond that — all the cost of a planner and none of the benefit.

So the controller starts in the behaviour layer, and watches its own progress:

if new cells mapped over the last 100 s ≈ 0 → frontier exploration
else → biased random walk with wall-following

The random walk gets a rough map cheaply. When it stalls — which it does, once it has seen everything within easy reach — the planner takes over precisely when it has something worth planning over. And when frontier exploration is defeated three times by the reactive layer (a "false frontier": a boundary that turns out to be unreachable), it hands control back.

The sensing has its own compromise worth recording. The Kinect returns a 2-D depth image; GMapping wants a laser scan. The controller takes a single horizontal slice from the middle of the image and treats it as a 1-D range array — throwing away almost all the depth data to fit an interface. It works, and it is also why a table edge at chest height is invisible to the map and only ever discovered by a bumper.

Reactive

3 bumpers, 180°
Contact → reverse and turn
Pre-empts everything

Behaviour

Kinect slice, 57°
Wall-follow, turn to open space
The default mode

Deliberate

Occupancy grid
Nearest frontier + path
Only once there is a map

The map each strategy built in the same room — **Same room, same clock, four controllers.** Cream is confirmed floor, red is seen obstacle, grey is still unknown.

Nobody wins

Six randomly generated rooms, 300 seconds each, all four controllers on every one, everything in scripts/tools/run_explore.py. I expected a ranking. What came out is more useful than a ranking.

Strategy	mean coverage	spread (sd)	worst room	best room	time to half the floor
biased random walk	62.1 %	± 9.4	46.1 %	71.5 %	177 s (1/6 never)
reactive wall-following	60.0 %	± 23.7	25.6 %	92.2 %	42 s (2/6 never)
frontier exploration	51.7 %	± 20.7	13.2 %	76.7 %	9 s (3/6 never)
hybrid (the contest controller)	63.0 %	± 33.2	11.2 %	99.2 %	36 s (2/6 never)

← swipe the table →

1

The means are a coin toss. The variance is the whole story.

62.1 %, 60.0 %, 51.7 %, 63.0 % — across six rooms the four controllers are separated by less than their own standard deviations, and the hybrid's nominal win over a random walk is nine tenths of a percent. If the contest had been scored on one room, the winner would have been whichever robot got the lucky floor plan.

What actually separates them is consistency. The random walk has a spread of ±9.4 and never does better than 71.5 % or worse than 46.1 %. The hybrid has a spread of ±33.2, ranging from 11.2 % to 99.2 %. It is simultaneously the best controller and the worst one, depending on the room.

2

The switching rule is the risk

Look at where the hybrid fails. In rooms 3 and 4 it scores 11.2 % and 24.0 % while plain reactive wall-following — which is what the hybrid does until it decides otherwise — scores 71.2 % and 81.4 %. The hybrid did not lose because frontier exploration is bad. It lost because the stall detector fired while the behaviour layer was doing fine, handed control to a planner that then did worse, and the hybrid can only be as good as its worst decision about which mode to be in.

When the detector is right — rooms 0, 1, 2 and 5 — the hybrid beats every single-strategy controller, by up to 62 points. Composing controllers does not average their performance; it multiplies the best case and the worst case both.

Coverage against time for all four strategies — **Coverage against time, six rooms, mean ± one standard deviation.** The bands overlap for the entire run. Note how early frontier's curve rises and how early it flattens — it is the fastest to half a room and the least likely to ever get there.

3

Nearest-frontier has a trap in it, and it costs 57 points

The obvious implementation of frontier exploration — BFS from the robot to the nearest cell bordering unknown space, then drive there — does not work at all. The nearest such cell is always the one just past the edge of the current sensor footprint, five centimetres away. The robot arrives instantly, re-plans to another one five centimetres beyond that, and never travels anywhere. Naive nearest-frontier scored 13 % coverage against 70 % for a random walk.

Two changes fix it, and both are in the report if you read it carefully. Require the goal to be at least a body length away, so the planner is planning rather than twitching. And follow the planned path rather than driving at the goal in a straight line — the report says "a targeted frontier point and a path are calculated", and the path is the part that matters, because a straight line wedges on the first obstacle between here and there.

Final coverage and time to half coverage, by strategy — **Coverage and speed are different questions.** Frontier exploration reaches half the floor in 9 seconds when it reaches it at all — and in three rooms out of six it never does. Reactive wall-following is slower to start and finishes further.

Reproduce it

# NumPy and matplotlib only git clone https://github.com/thejerrycheng/turtlebot-exploration cd turtlebot-exploration python scripts/tools/run_explore.py --rooms 6 # three figures + results JSON

The sandbox runs assets/js/turtlebot_explore.js — the same grid resolution, field of view, speeds and four controllers as scripts/tools/explore.py. The ROS stack that ran on the real TurtleBot (GMapping, the bumper callbacks, the Kinect slice) is in the contest report; this harness reproduces the exploration logic rather than the ROS plumbing, because the exploration logic is what the contest was actually about.

Credits

MIE443: Mechatronics Systems Design and Integration at the University of Toronto. Contest 1 (autonomous exploration) with Maryam Hosseini, Yuntao Cai, Yicheng Wang and Qingyun (Ada) Yang; Contest 2 added object recognition and a CNN for seven-class emotion recognition.

The ROS controller, the state machine and the contest runs are from the course. The six-room study, the three findings above and the browser sandbox were built afterwards.

Contest reports Code All projects