Category Archives: Robot Motion Planning

A theoretical framework based on hybrid models and logical verification to prove the guarantees for obstacle avoidance in mobile robot navigation

Stefan Mitsch, Khalil Ghorbal, David Vogelbacher, and André Platzer, Formal verification of obstacle avoidance and navigation of ground robots, The International Journal of Robotics Research Vol 36, Issue 12, pp. 1312 – 1340, DOI: 0.1177/0278364917733549.

This article answers fundamental safety questions for ground robot navigation: under which circumstances does which control decision make a ground robot safely avoid obstacles? Unsurprisingly, the answer depends on the exact formulation of the safety objective, as well as the physical capabilities and limitations of the robot and the obstacles. Because uncertainties about the exact future behavior of a robot’s environment make this a challenging problem, we formally verify corresponding controllers and provide rigorous safety proofs justifying why the robots can never collide with the obstacle in the respective physical model. To account for ground robots in which different physical phenomena are important, we analyze a series of increasingly strong properties of controllers for increasingly rich dynamics and identify the impact that the additional model parameters have on the required safety margins. We analyze and formally verify: (i) static safety, which ensures that no collisions can happen with stationary obstacles; (ii) passive safety, which ensures that no collisions can happen with stationary or moving obstacles while the robot moves; (iii) the stronger passive-friendly safety, in which the robot further maintains sufficient maneuvering distance for obstacles to avoid collision as well; and (iv) passive orientation safety, which allows for imperfect sensor coverage of the robot, i.e., the robot is aware that not everything in its environment will be visible. We formally prove that safety can be guaranteed despite sensor uncertainty and actuator perturbation. We complement these provably correct safety properties with liveness properties: we prove that provably safe motion is flexible enough to let the robot navigate waypoints and pass intersections. To account for the mixed influence of discrete control decisions and the continuous physical motion of the ground robot, we develop corresponding hybrid system models and use differential dynamic logic theorem-proving techniques to formally verify their correctness. Since these models identify a broad range of conditions under which control decisions are provably safe, our results apply to any control algorithm for ground robots with the same dynamics. As a demonstration, we also synthesize provably correct runtime monitor conditions that check the compliance of any control algorithm with the verified control decisions.

Real-time modification of user inputs in the teleoperation of an UAV in order to avoid obstacles with a reactive algorithm, transparently from the user control

Daman Bareiss, Joseph R. Bourne & Kam K. Leang, On-board model-based automatic collision avoidance: application in remotely-piloted unmanned aerial vehicles, Auton Robot (2017) 41:1539–1554, DOI: 10.1007/s10514-017-9614-4.

This paper focuses on real-world implementation and verification of a local, model-based stochastic automatic collision avoidance algorithm, with application in
remotely-piloted (tele-operated) unmanned aerial vehicles (UAVs). Automatic collision detection and avoidance for tele-operated UAVs can reduce the workload of pilots to allow them to focus on the task at hand, such as searching for victims in a search and rescue scenario following a natural disaster. The proposed algorithm takes the pilot’s input and exploits the robot’s dynamics to predict the robot’s trajectory for determining whether a collision will occur. Using on-board sensors for obstacle detection, if a collision is imminent, the algorithm modifies the pilot’s input to avoid the collision while attempting to maintain the pilot’s intent. The algorithm is implemented using a low-cost on-board computer, flight-control system, and a two-dimensional laser illuminated detection and ranging sensor for obstacle detection along the trajectory of the robot. The sensor data is processed using a split-and-merge segmentation algorithm and an approximate Minkowski difference. Results from flight tests demonstrate the algorithm’s capabilities for teleoperated collision-free control of an experimental UAV.

A method to model trajectories that captures its essential parameters (for comparisons, clustering, etc.)

W. Lin et al., “A Tube-and-Droplet-Based Approach for Representing and Analyzing Motion Trajectories,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 39, no. 8, pp. 1489-1503, Aug. 1 2017.DOI: 10.1109/TPAMI.2016.2608884.

Trajectory analysis is essential in many applications. In this paper, we address the problem of representing motion trajectories in a highly informative way, and consequently utilize it for analyzing trajectories. Our approach first leverages the complete information from given trajectories to construct a thermal transfer field which provides a context-rich way to describe the global motion pattern in a scene. Then, a 3D tube is derived which depicts an input trajectory by integrating its surrounding motion patterns contained in the thermal transfer field. The 3D tube effectively: 1) maintains the movement information of a trajectory, 2) embeds the complete contextual motion pattern around a trajectory, 3) visualizes information about a trajectory in a clear and unified way. We further introduce a droplet-based process. It derives a droplet vector from a 3D tube, so as to characterize the high-dimensional 3D tube information in a simple but effective way. Finally, we apply our tube-and-droplet representation to trajectory analysis applications including trajectory clustering, trajectory classification & abnormality detection, and 3D action recognition. Experimental comparisons with state-of-the-art algorithms demonstrate the effectiveness of our approach.

Several strategies for exploring unknown environments based on graphs extracted from Voronoi diagrams

E. G. Tsardoulias, A. Iliakopoulou, A. Kargakos, L. Petrou, Cost-Based Target Selection Techniques Towards Full Space Exploration and Coverage for USAR applications in a Priori Unknown Environments, J Intell Robot Syst (2017) 87:313–340, DOI: 10.1007/s10846-016-0434-0.

Full coverage and exploration of an environment is essential in robot rescue operations where victim identification is required. Three methods of target selection towards full exploration and coverage of an unknown space oriented for Urban Search and Rescue (USAR) applications have been developed. These are the Selection of the closest topological node, the Selection of the minimum cost topological node and the Selection of the minimum cost sub-graph. All methods employ a topological graph extracted from the Generalized Voronoi Diagram (GVD), in order to select the next best target during exploration. The first method utilizes a distance metric for determining the next best target whereas the Selection of the minimum cost topological node method assigns four different weights on the graph’s nodes, based on certain environmental attributes. The Selection of the minimum cost sub-graph uses a similar technique, but instead of single nodes, sets of graph nodes are examined. In addition, a modification of A* algorithm for biased path creation towards uncovered areas, aiming at a faster spatial coverage, is introduced. The proposed methods’ performance is verified by experiments conducted in two heterogeneous simulated environments. Finally, the results are compared with two common exploration methods.

Prediction of changes in behaviors of cars for autohomous driving, based on POMDPs made efficient by separation of multiple policies

Enric Galceran, Alexander G. Cunningham, Ryan M. Eustice, Edwin Olson,Multipolicy decision-making for autonomous driving via changepoint-based behavior prediction: Theory and experiment, Autonomous Robots, August 2017, Volume 41, Issue 6, pp 1367–1382, DOI: 10.1007/s10514-017-9619-z.

This paper reports on an integrated inference and decision-making approach for autonomous driving that models vehicle behavior for both our vehicle and nearby vehicles as a discrete set of closed-loop policies. Each policy captures a distinct high-level behavior and intention, such as driving along a lane or turning at an intersection. We first employ Bayesian changepoint detection on the observed history of nearby cars to estimate the distribution over potential policies that each nearby car might be executing. We then sample policy assignments from these distributions to obtain high-likelihood actions for each participating vehicle, and perform closed-loop forward simulation to predict the outcome for each sampled policy assignment. After evaluating these predicted outcomes, we execute the policy with the maximum expected reward value. We validate behavioral prediction and decision-making using simulated and real-world experiments.

Qualitative robot navigation

Sergio Miguel-Tomé, Navigation through unknown and dynamic open spaces using topological notions, Connection Science, DOI: 10.1080/09540091.2016.1277691.

Until now, most algorithms used for navigation have had the purpose of directing system towards one point in space. However, humans communicate tasks by specifying spatial relations among elements or places. In addition, the environments in which humans develop their activities are extremely dynamic. The only option that allows for successful navigation in dynamic and unknown environments is making real-time decisions. Therefore, robots capable of collaborating closely with human beings must be able to make decisions based on the local information registered by the sensors and interpret and express spatial relations. Furthermore, when one person is asked to perform a task in an environment, this task is communicated given a category of goals so the person does not need to be supervised. Thus, two problems appear when one wants to create multifunctional robots: how to navigate in dynamic and unknown environments using spatial relations and how to accomplish this without supervision. In this article, a new architecture to address the two cited problems is presented, called the topological qualitative navigation architecture. In previous works, a qualitative heuristic called the heuristic of topological qualitative semantics (HTQS) has been developed to establish and identify spatial relations. However, that heuristic only allows for establishing one spatial relation with a specific object. In contrast, navigation requires a temporal sequence of goals with different objects. The new architecture attains continuous generation of goals and resolves them using HTQS. Thus, the new architecture achieves autonomous navigation in dynamic or unknown open environments.

A nice summary of motion planning

J. J. M. Lunenburg, S. A. M. Coenen, G. J. L. Naus, M. J. G. van de Molengraft and M. Steinbuch, “Motion Planning for Mobile Robots: A Method for the Selection of a Combination of Motion-Planning Algorithms,” in IEEE Robotics & Automation Magazine, vol. 23, no. 4, pp. 107-117, Dec. 2016. DOI: 10.1109/MRA.2015.2510798.

A motion planner for mobile robots is commonly built out of a number of algorithms that solve the two steps of motion planning: 1) representing the robot and its environment and 2) searching a path through the represented environment. However, the available literature on motion planning lacks a generic methodology to arrive at a combination of representations and search algorithm classes for a practical application. This article presents a method to select appropriate algorithm classes that solve both the steps of motion planning and to select a suitable approach to combine those algorithm classes. The method is verified by comparing its outcome with three different motion planners that have been successfully applied on robots in practice.

Survey and taxonomy of path planning algorithms

Thi Thoa Mac, Cosmin Copot, Duc Trung Tran, Robin De Keyser, Heuristic approaches in robot path planning: A survey, Robotics and Autonomous Systems, Volume 86, 2016, Pages 13-28, ISSN 0921-8890, DOI: 10.1016/j.robot.2016.08.001.

Autonomous navigation of a robot is a promising research domain due to its extensive applications. The navigation consists of four essential requirements known as perception, localization, cognition and path planning, and motion control in which path planning is the most important and interesting part. The proposed path planning techniques are classified into two main categories: classical methods and heuristic methods. The classical methods consist of cell decomposition, potential field method, subgoal network and road map. The approaches are simple; however, they commonly consume expensive computation and may possibly fail when the robot confronts with uncertainty. This survey concentrates on heuristic-based algorithms in robot path planning which are comprised of neural network, fuzzy logic, nature-inspired algorithms and hybrid algorithms. In addition, potential field method is also considered due to the good results. The strengths and drawbacks of each algorithm are discussed and future outline is provided.

Combining efficiently symbolic planning with geometric planning

Fabien Lagriffoul, Benjamin Andres (2016), Combining task and motion planning: A culprit detection problem , The International Journal of Robotics Research, Vol 35, Issue 8, pp. 890 – 927, DOI: 10.1177/0278364915619022.

Solving problems combining task and motion planning requires searching across a symbolic search space and a geometric search space. Because of the semantic gap between symbolic and geometric representations, symbolic sequences of actions are not guaranteed to be geometrically feasible. This compels us to search in the combined search space, in which frequent backtracks between symbolic and geometric levels make the search inefficient. We address this problem by guiding symbolic search with rich information extracted from the geometric level through culprit detection mechanisms.

Real-time trajectory generation for omnidirectional robots, and a good set of basic bibliographical references

Tamás Kalmár-Nagy, Real-time trajectory generation for omni-directional vehicles by constrained dynamic inversion, Mechatronics, Volume 35, May 2016, Pages 44-53, ISSN 0957-4158, DOI: 10.1016/j.mechatronics.2015.12.004.

This paper presents a computationally efficient algorithm for real-time trajectory generation for omni-directional vehicles. The algorithm uses a dynamic inversion based approach that incorporates vehicle dynamics, actuator saturation and bounded acceleration. The algorithm is compared with other trajectory generation algorithms for omni-directional vehicles. The method yields good quality trajectories and is implementable in real-time. Numerical and hardware tests are presented.