The Robotics Institute

RI | Centers | CFR | Seminar

Foundations of Robotics Seminar, November 24, 2008
Time and Place | Seminar Abstract


 

Survivability: Measuring and Ensuring Path Diversity  

Lawrence H. Erickson

PhD student

Department of Computer Science - University of Illinois

(based on the ICRA 2009 submission by Lawrence H. Erickson and Steven M. LaValle)

 

and

 

 

Path Diversity Is Only Part of the Problem  

Ross A. Knepper (Matthew Mason)

PhD student
Robotics Institute - Carnegie Mellon Univeristy

(based on the ICRA 2009 submission by Ross A. Knepper and Matthew T. Mason)


 

 

Time and Place

Wean Hall 5316
Talk 4:00 pm

Abstract

 

Measuring and Ensuring Path Diversity

A novel criterion is introduced for assessing the diversity of a collection of paths or trajectories. The main idea is the notion of survivability, which measures the likelihood that numerous paths are obstructed by the same obstacle. This helps to improve robustness with respect to collision, which is an important challenge in the design of real-time planning algorithms. Efficient algorithms are presented for computing the survivability criterion and for selecting a subset of paths that optimize survivability from a larger collection. The algorithms are implemented and solutions are illustrated for four different systems. Chi-square tests are used to show uniform coverage obtained by using the computed paths in a simple breadth-first search. Random obstacle placement is used to show superior robustness of these primitives compared to uniform sampling of the control space.


Path Diversity Is Only Part of the Problem

The goal of motion planning is to find a feasible path between two positions that is free from collision with obstacles. Path sets are a robust approach to this problem in the face of real-world complexity and uncertainty. A path set is a collection of feasible paths and their corresponding control sequences. A path-set-based planner navigates by repeatedly testing each of these robot-fixed paths for collision with obsta- cles. A heuristic function selects which of the surviving paths to follow next. A path set possesses high path diversity if it performs well at obstacle-avoidance and goal-seeking behaviors. Previous work in path diversity has tacitly assumed that a correlation exists between this dynamic planning problem and a simpler, static path diversity problem: a robot placed randomly into an obstacle field evaluates its path set for collision without moving. Although an intuitive connection exists between these two problems, this paper shows that static and dynamic path diversity are two distinct properties. After empirically demonstrating this fact, we discuss some of the factors that differentiate the two problems.


The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.