Guaranteeing Motion Safety for Robots A workshop of the 2011 Robotics: Science and Systems Conference -- Los Angeles, CA (US) -- June 27, 2011 Mon, 04 Jul 2011 13:08:14 +0000 en hourly 1 Abstracts Fri, 28 Jan 2011 10:00:00 +0000 frchard

  • Provably Safe Navigation for Mobile Robots with Limited Field-of-Views in Dynamic Environments

    Contributors: Thierry Fraichard and Sara Bouraine, INRIA Grenoble Rhone-Alpes (FR)

    Abstract: This talk addresses the problem of navigating in a provably safe manner a mobile robot with a limited field-of-view placed in a unknown dynamic environment. In such a situation, absolute motion safety (in the sense that no collision will ever take place whatever happens in the environment) is impossible to guarantee in general. It is therefore settled for a weaker level of motion safety dubbed passive motion safety: it guarantees that, if a collision is inevitable, the robot will be at rest. The main contribution of this paper is a reactive collision avoidance scheme called PassAvoid whose passive motion safety is guaranteed. At each time step, it computes a control that will keep the robot in safe states. The design of PassAvoid is based upon the concept of Inevitable Collision States (ICS), i.e. states for which, no matter what the future trajectory of the robot is, a collision eventually occurs. A passively safe version of the ICS concept is defined and used in PassAvoid.

  • Analyzing Safety for Mobile Robots in Partially Known Dynamic Indoor Environments

    Contributors: Bruno L’Espérance, Moslem Kazemi and Kamal Gupta, Simon Fraser University (CA)

    Abstract: In order for the general population to accept the introduction of robots in their everyday environment, the robotic systems need to have some sort of guarantee regarding safety. In environments populated with humans, collision between robots and humans should be avoided to the greatest extent possible. An immediate question then arises: is it possible to produce a method which will guarantee that no collision will occur, i.e., it will guarantee safety between robots and humans? The answer to this question usually depends on the assumptions made on the underlying environment and also on the actual definition of safety.Outline of the talk:

    • Overview existing notions in literature such as inevitable collision states (ICS) and how it makes it impossible to guarantee safety in unknown or partially unknown dynamic environments unless further assumptions about the environment are made.
    • Extend the definition of ICS to Possibly Inevitable Collision State (PICS) and furthermore, Possibly Inevitable Collision Configuration (PICC).
    • Explain how we can use PICC to verify the impossibility of guaranteeing safety.
    • Present our method to easily identify and compute PICC in a static map.
    • Give common examples of situations for which we cannot guarantee safety (these are not trap situations).
    • Main implication of our results is that we cannot guarantee safety even without trap situations.
    • Occlusion in the robots field of view plays a key role in PICC and we then discuss the implications of our results for design of buildings, rules for robots operating, etc. for scenarios where robots are to co-exist with humans.

  • Evaluating Reactive and Planning-based Approaches for Safe Decentralized Motion Coordination

    Contributors: Andrew Dobson, Athanasios Krontiris and Kostas Bekris, University of Nevada Reno (US)

    Abstract: This talk considers multiple cooperating dynamical systems trying to reach their individual goals in the same static environment without collisions, such as air-traffic management problems or car-like vehicles moving in a parking lot. These examples raise safety concerns, since the robots cannot stop instantaneously and must respect limits in the derivatives of their state parameters. Various safe reactive approaches with minimal information requirements have been proposed for such problems, such as the Generalized Roundabout Policy [Pallottino et al. IEEE TR'07] and Acceleration-Velocity Obstacles [van den Berg et al. ICRA '11]. The literature also provides a safety framework based on planning and the communication of future intentions by the robots [Grady et al., WAFR 10]. This talk evaluates these methods based on the following criteria: a) generality, b) information requirements, c) level of conservatism, d) the responsiveness of robots to unexpected changes in the environment, e) and deadlock avoidance guarantees.

  • Efficient, Yet Safe, Robot Motion Planning in Dynamic, Uncertain Environments

    Contributors: Noel du Toit and Joel Burdick, California Institute of Technology, Pasadena (US)

    Abstract: Motion safety is a basic requirement for robot autonomy, but is hard to evaluate in practical systems since the environment and system are not fully known a priori. Instead, the robot must rely on noisy measurements to estimate the world state, and plan through this partially known world. This uncertainty must be accounted for during motion planning, but requires careful definition of system safety. Early approaches to motion planning in uncertain environments sacrificed efficiency (performance) for conservatism (safety). However, these approaches are of limited use in complicated, cluttered scenarios due to this conservatism. In this work, a dynamic re-planning approach is combined with probabilistic collision checking (chance constraints) to obtain efficient, safe motion plans. This approximate algorithm accounts for anticipated measurements, resulting in more accurate predicted state distributions and thus more efficient solutions. Probabilistic collision checking, which accounts for both robot and object uncertainty, is used to evaluate constraints along the trajectory. Probabilistic safety (along this trajectory) is formulated in terms of a reaction horizon (i.e., number of stages required by the robot to react to changes in the environment) and is enforced by appropriately conditioning the chance constraints. The resulting approach allows the robot to navigate a dynamic, uncertain environment while avoiding obstacles and exhibiting safe, efficient behavior.

  • Worst-Case Deviations of Planned Trajectories for High-Speed Mobile Robots

    Contributors: Matthias Althoff and John Dolan, Carnegie Mellon University, Pittsburgh (US)

    Abstract: Most high-speed mobile robots, such as autonomous vehicles, have an on-board planner which generates a trajectory to be followed by a low-level controller. In order to check the safety of the planned maneuvers, one has to predict the areas occupied by the own vehicle and other vehicles. If those areas do not intersect for the time interval of the maneuver, the trajectory can be safely executed (an obligatory, but usually not executed braking maneuver is considered at the end of each maneuver to conclude safety for all times). Under the assumption that the controller ensures perfect trajectory following, the computation of the occupancy set of the own vehicle is simply obtained by translating and orientating the vehicle body along the planned trajectory. However, this procedure does not consider deviations caused by uncertainties such as uncertain measurements (GPS position, velocity), uncertain parameters (e.g. tire friction, vehicle load), and disturbances (e.g. slope, wind). In this talk, we present how to consider these uncertainties using efficient reachability analysis. A reachable set is considered as the set of all possible trajectories of the robot under the previously described uncertainties. This set makes it possible to properly enlarge the occupancy of the robot such that safety can be ensured under various uncertainties. The approach is efficient in the sense that the reachable sets can be computed on-board with sufficient update rates. Examples are presented for an autonomous vehicle.

  • Safe Avoidance of Dynamic Obstacles with Uncertain Motion Patterns

    Contributors: Jonathan How, Georges Aoude and Brandon Luders, Massachusetts Institute of Technology (US)

    Abstract: This talk will present a recently developed safe avoidance algorithm for environments with dynamic obstacles that have uncertain motion patterns. It is a real-time planning algorithm which guarantees probabilistic feasibility for autonomous robots subject to process noise and an uncertain environment, including dynamic obstacles with uncertain motion patterns. The algorithm incorporates chance-constrained rapidly-exploring random trees (CC-RRT), using chance constraints to explicitly incorporate probabilistic constraint satisfaction in the formulation while maintaining the computational benefits of sampling-based algorithms. The key contribution of the work is the inclusion of a novel method for modeling dynamic obstacles with uncertain future trajectories. The method, denoted as RR-GP, uses a learned motion pattern model of the dynamic obstacles to make long-term predictions of their future paths, such as discrete decisions at road intersections. This is done by combining the flexibility of Gaussian processes (GP), a nonparametric Bayesian model representing a distribution over trajectories, with the efficiency of RRT-Reach, a sampling-based reachability computation method which ensures dynamic feasibility.

  • Guaranteeing Safety in Modern High-Performance Autonomous Systems

    Contributors: Anil Aswani, Patrick Bouffard, Jeremy Gillula and Claire Tomlin, University of California Berkeley (US)

    Abstract: Modern robotic systems are becoming increasingly complex and more capable of accomplishing sophisticated tasks. Frequently, these systems are able to push the boundaries of performance by incorporating non-traditional control methods, such as using machine learning techniques or by using humans in-the-loop. Of course even in such high-performance systems making safety guarantees a priori is still a critical task, potentially made even more difficult by the complicated control schemes used. One way to overcome this difficulty is through the use of Hamilton-Jacobi reachability, which can be used to compute guaranteed safe and unsafe states for a system regardless of the control scheme used (as long as the disturbances and control authority of the system are bounded). The flexibility of this scheme has allowed it to be used in a wide variety of applications and systems; in this talk we will show how reachability techniques can be used not only to guarantee obstacle avoidance, but also how they can be used to guarantee safety in robotic systems that use machine learning to generate dynamic models on-the-fly, or even how they can be used to make safety guarantees in complicated multi-stage games.

  • Provably-correct Sampling-based Algorithms for Motion Planning Problems with Complex Task Specifications

    Contributors: Sertac Karaman and Emilio Frazzoli, Massachusetts Institute of Technology (US)

    Abstract: As engineering systems are becoming more complex, verification and validation of their design, e.g., to ensure safety, is becoming increasingly more important. Most recently, advances in formal verification have allowed the integration of automatic verification into the design of safety-critical real-time planning and control systems. In fact, several algorithms for provably-correct design of control systems have been proposed. However, the existing approaches either quickly become computationally intractable (e.g., with increasing dimensionality of the state space) or they fail to offer any completeness guarantees.In this talk, we develop a computationally-efficient approach for provably-correct design of motion plans with probabilistic completeness guarantees. This approach extends incremental sampling-based motion planning algorithms in a novel direction: motion planning to satisfy complex task specifications other than the usual “reach the goal region while avoiding collision with obstacles.” To specify a wide class of complex tasks, we use the deterministic mu-calculus, which is more expressive than the widely-used Linear Temporal Logic (LTL). We propose an algorithm based on the Rapidly-exploring Random Graphs (RRGs) and a novel incremental model checking algorithm. We show that our algorithm is probabilistically complete in the following sense: if there exists a trajectory of the system that satisfies the given mu-calculus specification, then our algorithm finds such a trajectory in finitely many iterations with probability one. Moreover, the computational complexity of our algorithm is a constant factor of that of the widely-used incremental sampling-based algorithms such as the RRT, which can only handle far simpler task specifications. We also present recent advances in sampling-based algorithms for optimal motion planning. In particular, we introduce the RRT*, an asymptotically-optimal incremental sampling-based algorithm, and present its applications to systems with complex kinodynamic constraints and high-dimensional state spaces. We discuss the role of optimality in motion planning problems with complex task specifications.

  • Guaranteed Safety: a Collision Avoidance Algorithm Designed for Provability and Computer-Aided Verification

    Contributor: Holger Taeubig, German Research Center for Artificial Intelligence, Bremen (DE)

    Abstract: When autonomous robots begin to share the human living and working spaces, safety becomes paramount. It is legally required that the safety of such systems is ensured. Throughout our project SAMS we were concerned with designing, implementing, and certifying a collision avoidance safety function for autonomous vehicles and robots according to IEC 61508 (SIL 3). The safety function calculates a safety zone for the robot, e.g. an automated guided vehicle, depending on its current motion, which is as large as required but as small as feasible. We specifically designed the algorithm with safety in mind and formally verified the functional correctness of its implementation. The formal proof was used as a major means of ensuring and documenting functional safety in the certification process. The talk will focus on the mathematically rigorous safety zone computation, which was crucial for realizing a formal proof. We will sketch basic proof arguments and give examples of our concrete code specification. This is intended to highlight the issues that arise from a developers point of view when formal verification is applied. Further, we will outline an extension of the basic concept to 3d collision avoidance, which we are currently working on, and discuss its potential applications and limits related to the availability of appropriate sensors.

  • Bio-Inspired Reactive Deconfliction and Stabilization

    Contributor: Kristi Morgansen, University of Washington (US)

    Abstract: Maneuvering around obstacles to safely reach a goal can be approached using trajectory planning, or deliberative, methods when sufficient advanced knowledge of the objects is available. However, for robust performance, both natural and engineered systems must have the ability to react on extremely short time scales to sudden, unexpected or unmodeled disturbances. A number of approaches have been constructed for engineered systems, but these methods do not demonstrate the reaction capabilities of biological systems. To construct appropriate engineering algorithms for obstacle avoidance based on biological data, we are working to combine biological models of sensor placement, range and bandwidth with engineering studies of optimal sensor placement and integration based on control theoretic observability results to encode basic biological principles into engineering algorithms for deconfliction and obstacle avoidance with probabilistic bounds on guaranteed performance. The end result will be an algorithmic framework with both significantly improved engineering performance and a deeper understanding of biological methods and capabilities.

  • Adaptive Time Horizon for On-Line Obstacle Avoidance in Dynamic Environments

    Contributors: Zvi Shiller, Oren Gal and Ariel Raz, Ariel University Center (IL)

    Abstract: This talk addresses the issue of motion planning in dynamic environments using Velocity Obstacles. Specifically, we propose an adaptive time horizon to truncate the velocity obstacle so that the boundary of the velocity obstacle closely approximates the boundary of the set of inevitable collision states. This ensures that any velocity vector that does not penetrate the velocity obstacle is safe, and any that does is not. Such clear partitioning between safe and unsafe velocities allows safe planning with only one step look ahead, and can produce near optimal trajectories, compared to the conservative trajectories produced when using an infinite time horizon. The computation of the adaptive time horizon is formulated as a minimum time problem, which is solved numerically for each static or moving obstacle. It is 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.

  • Quadric Surface-Based Collision Avoidance Strategies for Motion Safety in 3-D Environments

    Contributors: Animesh Chakravarthy, Wichita State University (US), and Debasish Ghose, Indian Institute of Science, Bangalore (IN)

    Abstract: Most of the existing literature on collision avoidance in 3-D assumes the objects to be modeled as spheres. While the spherical bounding box is valid in many cases, there are many other instances of object shapes where an ellipsoidal or a hyperboloid-like bounding box would be more appropriate in that it would lead to a tighter bounding box than a sphere. Discretizing such objects by a series of planes and computing the avoidance conditions for the entire object on the basis of the avoidance conditions on each such plane is not only computationally expensive – it also cannot give guarantees for collision avoidance with the original object. This paper considers the problem of motion safety by the use of collision cones for such quadric surfaces. The paper will discuss the design of guaranteed safe maneuver strategies based on game theoretical concepts and reachability sets. Possible future maneuvers of the vehicles will be taken into account to quantify possibility of collision, and cooperative and non-cooperative security strategies will be proposed. The computational issues related to the implementation of these strategies will also be discussed.

  • ]]> 0
    Program Mon, 14 Sep 2009 14:20:45 +0000 frchard
  • 08:45-09:00: Greetings of the participants
  • 09:00-10:30: Session 1
    1. Provably Safe Navigation for Mobile Robots with Limited Field-of-Views in Dynamic Environments. Thierry Fraichard, INRIA Grenoble Rhone-Alpes (FR)
    2. Analyzing Safety for Mobile Robots in Partially Known Dynamic Indoor Environments. Bruno L’Esperance, Simon Fraser University (CA)
    3. Evaluating Reactive and Planning-based Approaches for Safe Decentralized Motion Coordination. Kostas Bekris, University of Nevada Reno (US)
  • 10:30-10:45: Coffee break
  • 10:45-12:15: Session 2
    1. Efficient, Yet Safe, Robot Motion Planning in Dynamic, Uncertain Environments. Joel Burdick, California Institute of Technology, Pasadena (US)
    2. Worst-Case Deviations of Planned Trajectories for High-Speed Mobile Robots. Matthias Althoff, Carnegie Mellon University, Pittsburgh (US)
    3. Safe Avoidance of Dynamic Obstacles with Uncertain Motion Patterns. Jonathan How, Massachusetts Institute of Technology (US)
  • 12:15-13:30: Lunch break
  • 13:30-15:00: Session 3
    1. Guaranteeing Safety in Modern High-Performance Autonomous Systems. Jeremy Gillula and Patrick Bouffard, University of California Berkeley (US)
    2. Provably-Correct Sampling-based Algorithms for Motion Planning Problems with Complex Task Specifications. Sertac Karaman, Massachusetts Institute of Technology (US)
    3. Guaranteed Safety: a Collision Avoidance Algorithm Designed for Provability and Computer-Aided Verification. Holger Taeubig, German Research Center for Artificial Intelligence, Bremen (DE)
  • 15:00-15:30: Coffee break
  • 15:30-17:00: Session 4
    1. Bio-Inspired Reactive Deconfliction and Stabilization. Kristi Morgansen, University of Washington (US)
    2. Adaptive Time Horizon for On-Line Obstacle Avoidance in Dynamic Environments. Zvi Shiller, Ariel University Center (IL)
    3. Quadric Surface-Based Collision Avoidance Strategies for Motion Safety in 3-D Environments. Animesh Chakravarthy, Wichita State University (US)
  • Location

    • USC Campus, Grace Ford Salvatori Building (GFS), room 109
    ]]> 0
    Presentations and Videos Mon, 14 Sep 2009 13:18:34 +0000 frchard
  • Provably Safe Navigation for Mobile Robots with Limited Field-of-Views in Dynamic Environments, Thierry Fraichard
  • Analyzing Safety for Mobile Robots in Partially Known Dynamic Indoor Environments, Bruno L’Esperance
  • Evaluating Reactive and Planning-based Approaches for Safe Decentralized Motion Coordination, Kostas Bekris
  • Efficient, Yet Safe, Robot Motion Planning in Dynamic, Uncertain Environments, Joel Burdick
  • Worst-Case Deviations of Planned Trajectories for High-Speed Mobile Robots, Matthias Althoff
  • Safe Avoidance of Dynamic Obstacles with Uncertain Motion Patterns, Jonathan How
  • Guaranteeing Safety in Modern High-Performance Autonomous Systems, Jeremy Gillula and Patrick Bouffard
  • Provably-Correct Sampling-based Algorithms for Motion Planning Problems with Complex Task Specifications, Sertac Karaman
  • Guaranteed Safety: a Collision Avoidance Algorithm Designed for Provability and Computer-Aided Verification, Holger Taeubig
  • Bio-Inspired Reactive Deconfliction and Stabilization, Kristi Morgansen
  • Adaptive Time Horizon for On-Line Obstacle Avoidance in Dynamic Environments, Zvi Shiller
  • Quadric Surface-Based Collision Avoidance Strategies for Motion Safety in 3-D Environments, Animesh Chakravarthy
  • ]]> 0
    Home Mon, 14 Sep 2009 14:11:27 +0000 frchard Motivation and Objectives

    In the near future, it is expected that robotic systems will share the human living and working spaces: service robots and cybernetic transport systems are examples of two primary application areas.  The technology is now mature; we have already witnessed autonomous mobile robots guiding people in museums and automated cars driving on the road network.  While moving (especially at high speed), automated vehicles, mobile manipulators and humanoid robots can be potentially dangerous should a collision occur. Before letting such robotic systems transport or share space with people in a truly autonomous way, it is critical to assert and characterize their motion safety, i.e., their guaranteed ability to avoid collision.

    Roboticists have long been aware of the motion safety issue; there is a rich literature on collision avoidance schemes.  However, motion safety in the real world, especially for systems with interesting dynamics, remains an open problem.  Demonstrating that a robotic system is working properly on a limited set of experiments is not enough. If autonomous robotic systems are ever to be deployed among human beings on a large scale, there is a need to characterize the level of motion safety that can be achieved and/or to specify the conditions under which it can be guaranteed.

    The purpose of this workshop is to disseminate recent research advances in guaranteed motion safety for robotic systems operating in challenging situations, such as dynamic and uncertain environments and high-speed robotic systems.  Overall, the focus of the workshop is on motion safety in dynamic environments; topics include, but are not limited to:

    • Collision avoidance for mobile robots, manipulator arms or humanoids.
    • Multi-robot / reciprocal collision avoidance.
    • Multi-robot coordination, e.g. air or shipping traffic control.
    • Safe reactive motion planning / dynamic replanning approaches.
    • Safe motion for robotic systems with kinematic or dynamic constraints.
    • Control theoretic approaches to motion safety.
    • Deterministic and probabilistic approaches to motion safety.
    • Deadlock and livelock avoidance in safe multi-robot coordination.

    The workshop is a follow up to the workshop Guaranteeing Safe Navigation in Dynamic Environments that was successfully held during the 2010 Int. Conf. on Robotics and Automation (ICRA).  It focuses on papers based on sound theoretical frameworks that specifically address motion safety in a formal way.



    ]]> 0