Balancing State-Space Coverage in Planning with Dynamics

Balancing State-Space Coverage in Planning with Dynamics

Inevitable Collision States in Replanning with Sampling-based Algorithms Kostas Bekris Computer Science and Engineering May 7, ICRA 2010 Inevitable Collision States Introduced due to dynamics in problems that require recomputation of a path planning among unknown static obstacles exploration planning in dynamic environments

multi-agent challenges: pursuit-evasion problems or coordination problems Inevitable Collision States In dynamics environments motion constraints are not necessary to get ICS Different names in the literature: Obstacle Shadows Regions of Inevitable Collisions Inevitable Collision States [Reif, Sharir 85] [LaValle, Kuffner 01]

[Fraichard 04] Reactive Collision Avoidance Vector Field Histogram Dynamic Window [Borenstein, Korem 91] [Fox et al. 97] Nearness Diagram Navigation Velocity Obstacles

[Minguez, Montano 04] [Fiorini, Shiller 98] Replanning with a Global Algorithm For problems where the state-space can be effectively discretized D* family of algorithms [Stenz 95] [Koenig, Likhachev 02] Otherwise: Replanning with sampling-based algorithms Techniques that do not reason about safety [Leven, Hutchinson 02] [Bruce, Veloso 02] [Kallman, Mataric 02] [van den Berg, Ferguson, Kuffner 06] [ Ferguson, Kalra, Stentz 06] [Gayle, Klinger, Xavier 07] [Zucker, Kuffner, Branicky 07]

Techniques that reason about safety or deal with dynamics [Hsu, Kindel, Latombe, Rock 02] [Frazzoli, Dahleh, Feron 02] [Bruce, Veloso 03] [Fraichard, Asama 04 ] [Petti, Friachard 05] [Zucker 06] [Kalisiak, van den Panne 07] [Bekris, Kavraki 07] [Tsianos, Kavraki 08] [Chan, Kuffner, Zucker 08] [Vatcha, Xiao 08] Sampling-based Replanning Things to consider in relation to safety 1 The actual ICS checker state ICS checker ICS or not?

2 How is it integrated with the replanning scheme? 1a. Conservative, Safe ICS checker Computing whether a state is truly ICS or not: Requires reasoning over an infinite horizon Necessary to guarantee safety Requires the union of all ICS states for each obstacle Necessary to guarantee safety [Fraichard, Asama 04] Requires reasoning over all feasible plans of the robot 1a. Conservative, Safe ICS checker

Dealing with infeasibility - conservative approx.: If a state is safe for a subset of plans, then truly not ICS model of the environments evolution state ICS checker evasive maneuvers proven safe or not proven safe? [Fraichard, Asama 04] [Petti, Fraichard 05]

[Parthasarathi, Fraichard 05] [Fraichard 07] [Martinez-Gomez, Fraichard 08,09] 1b. Relaxing the guarantees Reduce guarantees and focus on efficiency [Zucker 06] Alternative motivation: [Chan, Kuffner, Zucker 08] prune states during single-shot planning One way to approximate: Finite horizon Consider the ICS of individual obstacles separately Precomputations and other approximations for polygonal environments

Define regions of potential collision and near-collision 1b. Relaxing the guarantees Or use learning: Use Support Vector Machines to learn a classifier [Kalisiak, van de Panne 07] 1. Schools of thought towards ICS 1 School of Complacency

Its not a real problem for my system 2 School of Computational Efficiency Many advantages of being computationally efficient You can search more during the same amount of time In real systems, you have uncertainty Why care about guarantees, when no real guarantees can be provided?

3 Conservative School of Safety Collision avoidance is the only guarantee we provide 1. Challenges for the future It is upon the people who believe that safety is critical to prove that ICS is indeed a major issue Benchmark problems on real systems are needed

How often being complacent about ICS leads to collisions? How conservative and slow are the solutions that provide safety? Do practically provide safety? Are fast, relaxed approximations sufficient? What about hybrid schemes? First quickly prune states with a classifier and among the safe ones apply conservative schemes 2. Use of ICS-checker in Replanning Given an ICS-checker

How do you use it in order to provide safety? Replanning / Partial Motion Planning Framework Complete planning problem replanning cycle 0 x 0 0 replanning cycle 1 x0

1 replanning cycle 2 x0 2 replanning cycle 3 x 3

0 x replanning cycle 4 4 0 x Time 5 0

2. Straightforward integration [Frazzoli, Dahleh, Feron 02] [Petti, Fraichard 05] G Time No need to know the duration of the planning cycle Whenever a problem arises, follow the evasive maneuver 2. Minimalistic approach [Bekris, Kavraki 07] G

Time For given or controlled duration of planning cycle Check only states which are candidates to be initial states 2. Minimalistic Approach Retain Tree [Bekris, Kavraki 07] Retain valid part of tree: The retained tree must be checked for safety Check safety currently executed path

execution horizon Example Example Example Example Comparison in Computational Cost Alternative Trajectories produced in 1 sec

100 Straightforward approach Minimalistic approach 10 DD Scene Meandros Car Scene Meandros DD Scene Labyrinth

Car Scene Labyrinth Multi-Agent Problems Trajectory computed from perfect prediction or communication A A C D

D D B A C C B B

Safe Multi-Robot Motion Coordination Goal VB C [Bekris, Tsianos, Kavraki 07,09] current contingency for C plan A1 states x(tN+2) Goal VA Initial state

x(tN+1) A plan A2 plan A3 current contingency for B Goal VC Safe Multi-Robot Motion Coordination Goal VB [Bekris, Tsianos, Kavraki 07,09]

C plan A1 Goal VA Initial state x(tN+1) A plan A3 plan A2 Goal VC

Safe Multi-Robot Motion Coordination Goal VB [Bekris, Tsianos, Kavraki 07,09] C Goal VA Initial state x(tN+1) A Goal VC

Safe Multi-Robot Motion Coordination Goal VB [Bekris, Tsianos, Kavraki 07,09] C Goal VA Initial state x(tN+1) A Goal VC

Importance of Safety 16 vehicles @ Labyrinth Averages over 10 experiments Without our safety requirements With Requirements Number of Vehicles Occurrence of 1st collision (in sec)

Success Rate Success Rate 2 287.10 10% 100% 4 21

0% 100% 8 3.67 0% 100% 16 3

0% 100% Percentage of successful exploration experiments Example Example Some extensions Safe multi-robot motion coordination on real systems Asynchronous coordination Evaluation of the best way to integrate ICS-checker

with replanning framework Safe reciprocal motion coordination Thank you for your attention! Kostas Bekris research is supported by: the National Science Foundation (CNS 0932423), the Office of Naval Research, the Nevada NASA Space Grant Consortium and internal funds by the University of Nevada, Reno

Recently Viewed Presentations

  • Generative Adversarial Nets - Middle East Technical University

    Generative Adversarial Nets - Middle East Technical University

    "Unsupervised representation learning with deep convolutional generative adversarial networks." arXiv preprint arXiv:1511.06434 (2015). [4] Ledig, Christian, et al. "Photo-realistic single image super-resolution using a generative adversarial network." arXiv.
  • EML4550 - Engineering Design Methods Engineering-Economics Overview, Economic

    EML4550 - Engineering Design Methods Engineering-Economics Overview, Economic

    Times New Roman Arial Monotype Sorts Arial Black Lecture 1_Lecture Microsoft Word Document Microsoft Equation 3.0 Microsoft Word Picture EML4550 - Engineering Design Methods Life-cycle Cost of a Product Economic Analysis of a Product or Investment Compound Interest Compound factors...
  • LCA in Sustainable Building: Fitting Tools to the

    LCA in Sustainable Building: Fitting Tools to the

    LCA-based level 3 whole building tool for use at the conceptual design stage. Shows environmental effects of changes in shape, design or material make-up of a building . Allows designers to optimize operating+embodied energy effects over the complete building life...
  • Project 2- Stock Option Pricing - University of Arizona

    Project 2- Stock Option Pricing - University of Arizona

    Times New Roman Arial Symbol Default Design Microsoft Equation 3.0 Project 2- Stock Option Pricing Compounding Compound Interest Compound Interest Discrete Compounding Yield for Discrete Compounding Yield for Discrete Compounding Discrete Compounding Example 1 Example1 Example 1 Discrete Compounding Example...
  • Brown vs. The Board of Education

    Brown vs. The Board of Education

    Brown vs. The Board of Education Dave Baniszewski Mike Bryant Helen Reyes David Rutledge EDUC 845 Liberty University Reagan Administration Emergency School Aid Act Los Angeles Segregation Desegregation Segregation Again Race & Gender 1988 Desegregation's High Water Mark Board of...
  • Training

    Training

    Grant aid awarded to students on the basis of financial need. Merit-Based Aid. Award usually remains the same over the course of the student's academic career while need-based aid can change based on families financial situation.
  • Chapter 18: Communication - NC State Computer Science

    Chapter 18: Communication - NC State Computer Science

    Chapter 18: Communication ... message type plus proposition Perlocution, or how it influences the recipient, e.g., turns on the air conditioner, opens the window, ignores the speaker Illocution is the core aspect Chapter 18 * Service-Oriented Computing: Semantics, Processes, Agents...
  • ELOHIM (God) The Self-Existing One - Bible Believers

    ELOHIM (God) The Self-Existing One - Bible Believers

    CHRIST & THE BRIDE REIGN IN THE MILLENNIUM - 1000 YEARS HONEYMOON ON EARTH - CHRIST PERFORMS ROLE AS THE SON OF DAVID GARDEN OF EDEN RESTORED FOR THE LAST ADAM AND HIS BRIDE The NEW HEAVEN AND EARTH REVELATION...