Guaranteeing Motion Safety for Robots

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.