Collaborative Mobile Robots

for High-Risk Urban Missions

$\Diamond\Diamond$

P.I.'s Leonidas J. Guibas, Jean-Claude Latombe

Computer Science Department, Stanford University

$\Diamond\Diamond$

Focus

• Investigate the automatic generation of motion strategies (robot motion planning, coordination, and execution techniques) for autonomously achieving information-gathering tasks in a building environment.

• Three distinct tasks are considered:

  • Map building

  • Target finding

  • Target tracking

Research Team

• P.I.'s: Leonidas Guibas, Jean-Claude Latombe

• Postdoctoral students:

  • T.M. Murali: map building, representations

  • Raphael Murrietta: experimental support, target tracking

• PhD students:

  • Hector Gonzalez: map building, target tracking

  • Cheng-yu Lee: target tracking

  • David Lin: target finding

Map Building

• Task: The robots have no (or partial) a priori map information. They deploy into the building and collect data to form a map.

• Goal: Generate efficient exploratory strategies, e.g., to minimize time for building a model (reduce travel path, reduce number of complex sensory operations).

• Method: Build 2-D map with a planar horizontal range finder, using a greedy next-best-view technique to reduce length of travel path. Exploit 2-D map to decide where to perform 3-D sensing operations.

Models for Map Building (1)

• Map:

  • Collection of 2-D layouts, with motion obstructing and/or visibility occluding obstacles: geometric + probabilistic representations.

  • Collection of partial 3-D models, with or without texture maps, and fixed digitized images from selected viewpoints.

  • Inclusion of landmark information for self-localization and navigation.

Models for Map Building (2)

• Sensors:

  • Range finder with 1-D or 2-D cone of vision, maximal and minimal range, and incidence constraints.

  • Color camera (optional), for generating texture maps and digitized images.

Planning for 3-D Map Building

Computed robot positions in a 2-D map: (a) with no visibility constraints; (b) with minimum incidence of 60degrees. The portions of walls seen from two positions are shown in solid lines in (c).

Target Finding

• Task: The robots sweep the building to detect and localize potential targets (humans). Targets are mobile and mostly unpredictable.

• Goal: Generate reliable motion strategies that prevent targets to sneak back in already cleared regions.

• Methods: (1) Decomposition of space into ``conservative'' cells. (2) Grid-based representation + heuristic search. (3) Greedy algorithms for multi-robot strategies.

Example of Target Finding Strategy

... with perfect line-of-sight visibility model.

Another Example of Target Finding Strategy

... with perfect line-of-sight visibility model.

Examples of Target Finding Strategies

... with perfect line-of-sight visibility model restricted to an orientable vision cone.

Models for Target Finding

• Sensors: cone of vision, sampling rate, size of target.

• Map: 2-D vs. 3-D.

• Mobility: error in self-localization of robots.

• Target behavior: maximal velocity of targets vs. robots.

Target Tracking

• Task: Once a target has been detected, the robots must maintain visibility with it by anticipate target moves (e.g., targets trying to hide behind obstacles) and coordinate their motions appropriately.

• Goal: Explore techniques to decide on-line how the robots should move to minimize the chances that detected targets get out of sight of any tracking robots.

• Method: Compute the next possible positions of the robots that will minimize the time-to-escape of the targets. Allow dynamic exchanges of targets among the robots.

Examples of Target Tracking

... with perfect visibility models.

Models for Target Tracking

• Sensors: cone of vision, sampling rate, size of target.

• Map: 2-D vs. 3-D.

• Mobility: error in self-localization of robots and localization of targets.

• Target behavior: maximal velocity of targets vs. robots.

Foreseeable problems

• Realistic models of sensing, mobility, ..., result in more complex map-building, target-finding, and target-tracking algorithms. What is the best tradeoff?

• Visibility computations in maps are key to efficient and reliable target finding and tracking. Are they possible? Can we use weaker visibility notions?

• On-line computations, incomplete data, communication maintenance, and robot survivability are not taken into account. Will our technique easily scale up to deal with those other issues?

• We still poorly understand the role of 3-D models in target finding and tracking. Can we compute robot motions using mostly 2-D floor plans?

Experimental Hardware

• 1 Nomad 200 robot equipped with laser range finder

• 1 Nomad 200 with camera for target finding/tracking

• 1 Nomad Super Scout with time-of-flight laser range finder

• 2 Nomad Super Scout with cameras for target finding/tracking

• All 5 robots are/will be equipped with additional cameras for landmark-based navigation

Task Schedule

Tasks	Q1	Q2	Q3	Q4	Q5	Q6	Q7	Q8
Map representation	X	X
Mobility model	X	X
Sensing model	X	X
Plan representation	X	X
Target behavior model	X	X
Map building	X	X	X	X	X	X	X	X
Target finding	X	X	X	X	X	X	X	X
Target tracking	X	X	X	X	X	X	X	X

Milestones for Map Building

• Q2: Next-best-view technique for multiple robots.

• Q3: Next-best-view technique for multiple robots, with large localization uncertainty.

• Q4: Randomized art-gallery technique to find robot locations for performing 3-D sensing operations.

Milestones for Target Finding

• Q3: Target finding with extended visibility model (simulation).

• Q5: Minimization of space where targets may still hide (simulation).

• Q6: Target-finding experiment with a single robot.

• Q7: Target-finding experiment with 2 robots, or more.

Milestones for Target Tracking

• Q4: Target-tracking experiment with one robot and one target.

• Q5: Target-tracking experiment with multiple robots and targets.

• Q6: Target-tracking experiment with 2 robots and a human target.

• Q7: Target-tracking experiment with 2 robots and 2 human targets.

Work done so far

• Environment, mobility, sensor, and target models, and plan representation $\Rightarrow$ 1/2 completed

• Next-best-view technique for map building $\Rightarrow$ beginning

• Robot placement for 3-D sensing (probabilistic art-gallery algorithm with extended visibility model) $\Rightarrow$ beginning

• Target finding with extended visibility models $\Rightarrow$ beginning

Enabling Technology for our Research

Our research will benefit from advances made by other groups on the following problems:

• For map building: Sensing techniques that extract geometric primitives (e.g., surface patches) from environment and identify/localize landmarks

• For target finding: Sensing techniques that identify and localize potential targets and reliable navigation techniques.

• For target tracking: Fast visual tracking of a target in an image sequence.