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
