Guaranteeing Safe Navigation in Dynamic Environments

Program

frchard — Mon, 14 Sep 2009 14:20:45 +0000

When and Where? Friday, May 7 from 9H00 to 12H30 in Egan Center Room 1

8h45-9h00: Greetings of the participants

9h00-9h30: Motion Safety in Dynamic Environments, an Introduction
Speakers: Thierry Fraichard & James Kuffner.

9h30-10h00: Optimal Reciprocal Collision Avoidance
Speaker: Dr. Jur Van Den Berg, University of California, Berkeley (US).
Abstract: We present a formal approach to reciprocal n-body collision avoidance, where multiple mobile robots need to avoid collisions with each other while moving in a common workspace. In our formulation, each robot acts fully independently, and does not communicate with other robots. Based on the definition of velocity obstacles, we derive sufficient conditions for collision-free motion by reducing the problem to solving a low-dimensional linear program. We test our approach on several dense and complex simulation scenarios involving thousands of robots and compute collision-free actions for all of them in only a few milliseconds. To the best of our knowledge, this method is the first that can guarantee local collision-free motion for a large number of robots in a cluttered workspace.

10h00-10h30: Distributed Reactive Collision Avoidance
Speaker: Dr. Emmett Lalish, University of Washington & Moiré Incorporated (US).
Abstract: Collision avoidance is an important aspect of multivehicle coordination because it prevents vehicles from disrupting or destroying each other. The work contained in this paper concerns a novel approach to the n-vehicle collision avoidance problem. The vehicle model used here allows for three-dimensional movement and represents a wide range of vehicles. The algorithm works in conjunction with any desired controller to guarantee all vehicles remain free of collisions while attempting to follow their desired control. This algorithm is reactive and distributed, making it well suited for real time applications, and explicitly accounts for actuation limits. A robustness analysis is presented which provides a means to account for delays and unmodeled dynamics. Robustness to an adversarial vehicle is also presented.

10h30-10h45: Coffee Break

10h45-11h15: The Nonlinear Velocity Obstacle Revisited: the Optimal Time Horizon
Speaker: Prof. Zvi Shiller, Ariel University Center (IL).
Abstract: This talk addresses the issue of motion safety in dynamic environments using Velocity Obstacles. Specifically, we propose the minimum time horizon for the velocity obstacle to ensure that the velocity obstacle consists only of inevitable collision states. Thus, using the velocity obstacle to select potential avoidance maneuvers would ensure that only safe maneuvers are being selected. The computation of the minimum time horizon is formulated as a minimum time problem, which is solved numerically for each static or moving obstacle. The ‘’safe” velocity obstacles are used in an on-line planner that generates near-time optimal trajectories to the goal. The planner is demonstrated for on-line motion planning in very crowded static and dynamic environments.

11h15-11h45: Detecting if a Robot Trajectory is Guaranteed Continuously Collision-Free in Unknown and Unpredictable Environments
Speaker: Prof. Jing Xiao, University of North Carolina, Charlotte (US).
Abstract: For a robot to operate in a completely unknown environment, where obstacles are unknown and whether and how they move are also unknown, motion planning is largely an open problem. One essential challenge is how to guarantee that a robot can safely navigate in such an environment. We introduce a general approach to detect in real-time, based on sensing, if a future robot trajectory, which is a curve in the unknown configuration-time space, will be guaranteed continuously collision-free or not, no matter how obstacles move. Our detection algorithm efficiently uses low-level sensor data directly. Our approach does not need to identify obstacles or assume any obstacle geometry, and as such, does not base detection on predicting obstacle movements or assuming possible ways of obstacle movements. It can be used by real-time motion planners for any robot, including mobile robots and manipulators, to guide the robot’s motion in unknown and unpredictable environments. As long as a robot is moving along a detected collision-free trajectory by our approach, its safety is guaranteed, i.e., it will not be hit by any obstacle.

11h45-12h15: Safety and Computational Efficiency Tradeoffs in Replanning with Sampling-based Planners
Speaker: Prof. Kostas Bekris, University of Nevada, Reno (US).
Abstract: Safety concerns arise when replanning for systems with non-trivial dynamics, where a locally collision-free trajectory results in Inevitable Collision States (ICS). One way to avoid ICS is to employ machine learning and create an ICS identifier to prune such states during planning. Alternatively, conservative methods, such as contingency-based schemes, prune all states that cannot be shown to be safe. The first alternative is faster during the online phase of replanning but the second scheme provides stricter guarantees. The computational performance of the planner is important and is related to the safety of the system. A faster planner provides a more diverse set of plans in the same amount of time but these plans are not useful if they are unsafe. This talk focuses on this tradeoff between safety and computational performance, specifically for sampling-based planners, and employs simulated experiments with second-order vehicles moving among unexpected obstacles and in dynamic environments.
12h15-12h30: Final discussion and conclusion

Proceedings

admin — Mon, 14 Sep 2009 13:18:34 +0000

Featured Articles:

Featured Presentations:

Home

frchard — Mon, 14 Sep 2009 14:11:27 +0000

Motivation and Objectives

In the near future, it is expected that robots will share the human living space: service robots and cybernetic transport systems being the two primary application areas. The technology is mature now; we have already witnessed autonomous mobile robots guiding people in museums and automated cars driving themselves around on the road network. In this respect, the 2007 DARPA Urban Challenge proved a very enlightening event. The challenge called for 11 automated cars to drive 96 kilometers through an urban environment amidst 50 human-driven vehicles. Six automated cars finished the race thus proving that autonomous urban driving could become a reality. More important (and less publicized) is the fact that a number of incidents took place during the event. Their consequences were limited because DARPA observers would freeze the automated cars whenever necessary… Clearly, autonomous robots the size and dynamics of that of the Urban Challenge are potentially dangerous for themselves and their environment (especially when driving at high-speed). Therefore, before letting such robotic systems transport people or move among people in a truly autonomous way, it is critical to assert and characterize their operational motion safety, i.e. their ability to avoid collision. Demonstrating that a robot is working alright on a limited set of experiments is not enough. If we ever want autonomous robots to be deployed among human beings on a large scale, we need to actually characterize the level of safety that can be achieved and to specify the conditions under which they can be guaranteed. The purpose of this workshop is precisely to explore these issues and to gather the researchers interested in the design of autonomous robots for which motion safety can actually be characterized.

The focus is on the decisional aspects of navigation in “real world” situations, i.e. open, dynamic and partially known environments, where motion safety remains a challenge. The workshop features presentations by leading researchers in the field.

Organization

Dr. Thierry Fraichard, INRIA Grenoble Rhone-Alpes (FR).
Prof. James Kuffner, The Robotics Institute, Carnegie Mellon University (US).