Transcript Mapping and Pursuit-Evasion Strategies For a Simple Wall

Mapping and Pursuit-Evasion Strategies For
a Simple Wall-Following Robot
Anna Yershova
Duke University Algorithms Seminar
April 20, 2010
The Main Theme:
Planning in Information Spaces
 Think about the devices we build that intermingle
sensors, actuators, and computers.
 They are completely blind to the world until we equip
them with sensors.
 All of their accomplishments rest on their ability to sift
through sensor data and make appropriate decisions.
References
IROS 2009 TUTORIAL
The 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems
Filtering and Planning in Information Spaces
Date: 11 October 2009, Time: 8:45-5:30
By: Steve LaValle, University of Illinois
References
Mapping and Pursuit-Evasion Strategies For a Simple Wall-Following Robot
Anna Yershova, Benjamin Tovar, Max Katsev, Robert Ghrist, and Steven M. LaValle
IEEE Transactions on Robotics, 2010, under review
Bitbots: Simple Robots Solving Complex Tasks
Anna Yershova, Benjamin Tovar, Robert Ghrist, and Steven M. LaValle,
In Proc. The Twentieth National Conference on Artificial Intelligence (AAAI 2005)
J. Barraquand and P. Ferbach. Motion planning with uncertainty:
The information space approach. In Proceedings IEEE International
Conference on Robotics & Automation, pages 1341–1348, 1995.
S. L. Laubach and J. W. Burdick. An autonomous sensor-based pathplanning
for planetary microrovers. In Proceedings IEEE International Conference on
Robotics & Automation, 1999.
A. Blum, P. Raghavan, and B. Schieber. Navigating in unfamiliar
geometric terrains. In Proceedings ACM Symposium on Computational
Geometry, pages 494–504, 1991.
S. Suri, E. Vicari, and P. Widmayer. Simple robots with minimal sensing:
From local visibility to global geometry. International Journal of Robotics
Research, 27(9):1055–1067, September 2008.
M. Blum and D. Kozen. On the power of the compass (or, why mazes
are easier to search than graphs). In Proceedings Annual Symposium on
Foundations of Computer Science, pages 132–142, 1978.
B. R. Donald. On information invariants in robotics. Artificial
Intelligence Journal, 72:217–304, 1995.
M. A. Erdmann. On motion planning with uncertainty. Master’s thesis,
Massachusetts Institute of Technology, Cambridge, MA, August 1984.
S. Thrun, W. Burgard, and D. Fox. Probabilistic Robotics. MIT Press,
Cambridge, MA, 2005.
Scenarios with Sensors Needed
Scenarios with Sensors Needed
Where are Sensors?
Classical vs. Sensor-Centric Computation
Definition of a Virtual Sensor
Definition of a Virtual Sensor
Simple Example
Imagine trying to infer the location of a point on a planar graph while
observing only a single coordinate.
This simple example involves a point moving along a graph that has four
Preimages
The Partition Induces by h
A Lattice of Partitions
The Sensor Lattice
The Main Theme:
Planning in Information Spaces
 It is tempting (and common) to introduce the most complete and
accurate sensors possible to eliminate uncertainties and learn a
detailed, complex model of the surrounding world.
 In contrast, our theme is to start with sensing first and then
understand what information is minimally needed to solve
specific tasks.
 If we can accomplish our mission without knowing certain details
about the world, then the overall system may be more simple and
robust.
Solving Complex Tasks with a
Simple Wall-Following Robot
 What kinds of global information can be learned and what
kinds of tasks can be accomplished with as little sensing and
actuation as possible.
 Imagine designing motion strategies for a simple, low-cost,
differential-drive robot.
The Robot Model
Actions
Sensor
reading
s
The Robot Implementation ($15 USD)
Movies:
http://www.cs.illinois.edu/homes/katsev1
/videos/
State, Action, and Observation Spaces
 The state space:
 Additional pebble sensor
and actions {DROP, GRAB}:
Information Spaces
 Although we assume that the state space is known, the
particular state will be, in general, unknown to the robot.
 We need to be precise about what information the robot has
available.
 Such information is called information space
 History I-space:
More Information Spaces
let ai = 1 if ui = LFOLLOW,
ai = −1 if ui = RFOLLOW,
and ai = 0 otherwise.
let wi = 1 if the pebble is detected,
and wi = 0 otherwise.
the total number of edges
traversed by the robot.
the distance traveled after
eliminating all reversals.
the number of times the pebble
has been contacted.
Simple Task:
Determining the Winding Number
Simple Task:
Counting Polygon Vertices
More Complex Task:
Learning the Environment Structure
The Cut Ordering:
Information Stored in Cut Ordering:
The Cut Diagram
Information Stored in Cut Ordering:
The Cut Diagram
Learning the Environment Structure:
The Cut Ordering
Learning the Environment Structure:
The Cut Ordering
 The robot can learn the cut ordering associated with E using O(n2)
actions and O(n) space, in which n is the number of vertices in ∂E.
 Without sensing a pebble, the robot cannot construct the cut ordering.
 Once the cut ordering has been learned, no additional combinatorial
information regarding the cut arrangement of E can be obtained.
More Complex Task: Pursuit-Evasion!
 Detect all unpredictably moving targets in the polygonal
environment.
State, Action, and Observation Spaces
 The state space:
 Additional detection sensor
Combinatorial Changes in Visibility
Information
Cut Diagram Contains the Visibility
Information
Cut Diagram Contains the Visibility
Information
Conservative Approximation of Bitangents
 let B(i, j) indicate whether there is a bitangent between vi and
vj .
 The proposition establishes a necessary (but not sufficient)
condition for B(i, j):
 For any pair, vi, vj, (reflex vertices) let C(i, j) be a
predicate indicating that they satisfy Proposition 11. If C(i,
j), then vi and vj are called a bitangent candidate.
Conservative Approximation of Bitangents
Pursuit-Evasion Strategy
 Any systematic search over the visibility polygon
components using the bitangent approximations
Simulation Results
 Movies:
http://www.cs.duke.edu/~yershova/movies/t5.mpg
http://www.cs.duke.edu/~yershova/movies/taz.mpg
Conclusions and Future Directions





Virtual sensors: The interface from physical sensor to filters
h : X → Y slices X into equivalence classes
All basic sensors embed into the sensor lattice
All planning problems live in an I-space
Design virtual sensors, filters, planning problems together around
a task.
 Particular examples are demonstrated on a simple wall-following
robot, and strategies are developed for solving complex tasks
 Localization and mapping
 Pursuit-evasion
Conclusions and Future Directions
Relationship to Theory of Computation:
Conclusions and Future Directions
Relationship to Computational Geometry:
Foundation of Robotics:
Where is our Theory?