Category Archives: Robot Motion Planning

A unifying framework for path planning in real-time (mainly for UAVs) and a nice summary of the state-of-the-art in modern path planning

September 19, 2018 08:42 ,

M. Murillo, G. SánchezL. GenzelisL. Giovanini, A Real-Time Path-Planning Algorithm based on Receding Horizon Techniques, Journal of Intelligent & Robotic Systems, September 2018, Volume 91, Issue 3–4, pp 445–457, DOI: 10.1007/s10846-017-0740-1.

In this article we present a real-time path-planning algorithm that can be used to generate optimal and feasible paths for any kind of unmanned vehicle (UV). The proposed algorithm is based on the use of a simplified particle vehicle (PV) model, which includes the basic dynamics and constraints of the UV, and an iterated non-linear model predictive control (NMPC) technique that computes the optimal velocity vector (magnitude and orientation angles) that allows the PV to move toward desired targets. The computed paths are guaranteed to be feasible for any UV because: i) the PV is configured with similar characteristics (dynamics and physical constraints) as the UV, and ii) the feasibility of the optimization problem is guaranteed by the use of the iterated NMPC algorithm. As demonstration of the capabilities of the proposed path-planning algorithm, we explore several simulation examples in different scenarios. We consider the existence of static and dynamic obstacles and a follower condition.

Posted in: Robot motion planning , Tagged: ,

Including the dynamics of the environment in robot motion planning (navigation)

September 4, 2018 15:10 ,

María-Teresa Lorente, Eduardo Owen, and Luis Montano, Model-based robocentric planning and navigation for dynamic environments, The International Journal of Robotics Research Vol 37, Issue 8, pp. 867 – 889 DOI: 10.1177/0278364918775520.

This work addresses a new technique of motion planning and navigation for differential-drive robots in dynamic environments. Static and dynamic objects are represented directly on the control space of the robot, where decisions on the best motion are made. A new model representing the dynamism and the prediction of the future behavior of the environment is defined, the dynamic object velocity space (DOVS). A formal definition of this model is provided, establishing the properties for its characterization. An analysis of its complexity, compared with other methods, is performed. The model contains information about the future behavior of obstacles, mapped on the robot control space. It allows planning of near-time-optimal safe motions within the visibility space horizon, not only for the current sampling period. Navigation strategies are developed based on the identification of situations in the model. The planned strategy is applied and updated for each sampling time, adapting to changes occurring in the scenario. The technique is evaluated in randomly generated simulated scenarios, based on metrics defined using safety and time-to-goal criteria. An evaluation in real-world experiments is also presented.

Posted in: Robot motion planning , Tagged:

A review on mobile robot navigation

July 25, 2018 08:15 ,

Tzafestas, S.G. , Mobile Robot Control and Navigation: A Global Overview,J Intell Robot Syst (2018) 91: 35 DOI: 10.1007/s10846-018-0805-9.

The aim of this paper is to provide a global overview of mobile robot control and navigation methodologies developed over the last decades. Mobile robots have been a substantial contributor to the welfare of modern society over the years, including the industrial, service, medical, and socialization sectors. The paper starts with a list of books on autonomous mobile robots and an overview of survey papers that cover a wide range of decision, control and navigation areas. The organization of the material follows the structure of the author’s recent book on mobile robot control. Thus, the following aspects of wheeled mobile robots are considered: kinematic modeling, dynamic modeling, conventional control, affine model-based control, invariant manifold-based control, model reference adaptive control, sliding-mode control, fuzzy and neural control, vision-based control, path and motion planning, localization and mapping, and control and software architectures.

Posted in: Robot motion planning , Tagged: ,

Evaluating the safeness of a motion plan for mobile robot navigation

June 12, 2018 07:54 ,

Brian Axelrod, Leslie Pack Kaelbling, and Tomás Lozano-Pérez Provably safe robot navigation with obstacle uncertainty, The International Journal of Robotics Research Vol 37, Issue 7 DOI: 10.1177/0278364918778338.

As drones and autonomous cars become more widespread, it is becoming increasingly important that robots can operate safely under realistic conditions. The noisy information fed into real systems means that robots must use estimates of the environment to plan navigation. Efficiently guaranteeing that the resulting motion plans are safe under these circumstances has proved difficult. We examine how to guarantee that a trajectory or policy has at most ϵ collision probability (ϵ-safe) with only imperfect observations of the environment. We examine the implications of various mathematical formalisms of safety and arrive at a mathematical notion of safety of a long-term execution, even when conditioned on observational information. We explore the idea of shadows that generalize the notion of a confidence set to estimated shapes and present a theorem that allows us to understand the relationship between shadows and their classical statistical equivalents such as confidence and credible sets. We present efficient algorithms that use shadows to prove that trajectories or policies are safe with much tighter bounds than in previous work. Notably, the complexity of the environment does not affect our method’s ability to evaluate whether a trajectory or policy is safe. We then use these safety-checking methods to design a safe variant of the rapidly exploring random tree (RRT) planning algorithm.

Posted in: Robot motion planning , Tagged:

A novel approach to avoid the minima problem in potential fields navigation

May 22, 2018 07:56 ,

Fedele, G., D’Alfonso, L., Chiaravalloti, F. et al., Obstacles Avoidance Based on Switching Potential Functions, J Intell Robot Syst (2018) 90: 387. DOI: 10.1007/s10846-017-0687-2.

In this paper, a novel path planning and obstacles avoidance method for a mobile robot is proposed. This method makes use of a switching strategy between the attractive potential of the target and a new helicoidal potential field which allows to bypass an obstacle by driving the robot around it. The new technique aims at overcoming the local minima problems of the well-known artificial potentials method, caused by the summation of two (or more) potential fields. In fact, in the proposed approach, only a single potential is used at a time. The resulting proposed technique uses only local information and ensures high robustness, in terms of achieved performance and computational complexity, w.r.t. the number of obstacles. Numerical simulations, together with comparisons with existing methods, confirm a very robust behavior of the method, also in the case of a framework with multiple obstacles.

Posted in: Robot motion planning , Tagged: ,

Socially acceptable collision avoidance

May 10, 2018 08:25 ,

Haoan Wang, Antonio Tota, Bilin Aksun-Guvenc, Levent Guvenc Real time implementation of socially acceptable collision avoidance of a low speed autonomous shuttle using the elastic band method, Mechatronics, Volume 50, 2018, Pages 341-355, DOI: 10.1016/j.mechatronics.2017.11.009.

This paper presents the real time implementation of socially acceptable collision avoidance using the elastic band method for low speed autonomous shuttles operating in high pedestrian density environments. The modeling and validation of the research autonomous vehicle used in the experimental implementation is presented first, followed by the details of the Hardware-In-the-Loop connected and autonomous vehicle simulator used. The socially acceptable collision avoidance algorithm is formulated using the elastic band method as an online, local path modification algorithm. Parameter space based robust feedback plus feedforward steering controller design is used. Model-in-the-loop, Hardware-In-the-Loop and road testing in a proving ground are used to demonstrate the effectiveness of the real time implementation of the elastic band based socially acceptable collision avoidance method of this paper.

Posted in: Robot motion planning , Tagged: , ,

A mathematical study of controllers that produce paths with beautfiul shapes to reach a target point by a unicycle vehicle

April 26, 2018 07:25 ,

T. Tripathy and A. Sinha, Unicycle With Only Range Input: An Array of Patterns, IEEE Transactions on Automatic Control, vol. 63, no. 5, pp. 1300-1312, DOI: 10.1109/TAC.2017.2736940.

The objective of this paper is to generate planar patterns using an autonomous agent modeled as a unicycle. The patterns are generated about a stationary point referred to as the target. To achieve the same, the paper proposes a family of control inputs that are continuous functions of range, which is the distance between the unicycle and the target. The paper studies in detail a characterization of the resulting trajectories, which are a plethora of patterns of parametric curves (circles, spirals, epicyclic curves like hypotrochoids) and more. These appealing patterns find applications in exploration, coverage, land mine detection, etc., where the target represents any point of interest like a landmark or a beacon. The paper also investigates the necessary conditions on the control laws in order to generate patterns of desired shapes and bounds. Furthermore, to generate desired patterns with arbitrary initial conditions, a switching strategy is proposed which is illustrated using an algorithm. The paper presents a series of simulations of appealing patterns generated using the proposed control laws.

Posted in: Control Engineering, Robot motion planning

A novel algorithm for coverage path planning with very strong guarantees

April 19, 2018 07:38 ,

J. Song and S. Gupta, $varepsilon ^{star }$: An Online Coverage Path Planning Algorithm, IEEE Transactions on Robotics, vol. 34, no. 2, pp. 526-533, DOI: 10.1109/TRO.2017.2780259.

This paper presents an algorithm called ε*, for online coverage path planning of unknown environment. The algorithm is built upon the concept of an Exploratory Turing Machine (ETM), which acts as a supervisor to the autonomous vehicle to guide it with adaptive navigation commands. The ETM generates a coverage path online using Multiscale Adaptive Potential Surfaces (MAPS), which are hierarchically structured and dynamically updated based on sensor information. The ε*-algorithm is computationally efficient, guarantees complete coverage, and does not suffer from the local extrema problem. Its performance is validated by 1) high-fidelity simulations on Player/Stage and 2) actual experiments in a laboratory setting on autonomous vehicles.

Posted in: Robot motion planning, Robot task planning , Tagged:

A novel motion planning algorithm for robot navigation taking into account the robot kinematic constraints and shape

March 28, 2018 09:18 ,

Muhannad Mujahed, Dirk Fischer, Bärbel Mertsching, Admissible gap navigation: A new collision avoidance approach, Robotics and Autonomous Systems,
Volume 103, 2018, Pages 93-110, DOI: 10.1016/j.robot.2018.02.008.

This paper proposes a new concept, the Admissible Gap (AG), for reactive collision avoidance. A gap is called admissible if it is possible to find a collision-free motion control that guides a robot through it, while respecting the vehicle constraints. By utilizing this concept, a new navigation approach was developed, achieving an outstanding performance in unknown dense environments. Unlike the widely used gap-based methods, our approach directly accounts for the exact shape and kinematics, rather than finding a direction solution and turning it later into a collision-free admissible motion. The key idea is to analyze the structure of obstacles and virtually locate an admissible gap, once traversed, the robot makes progress towards the goal. For this purpose, we introduce a strategy of traversing gaps that respect the kinematic constraints and provides a compromise between path length and motion safety. We also propose a new methodology for extracting gaps that eliminates useless ones, thus reducing oscillations. Experimental results along with performance evaluation demonstrate the outstanding behavior of the proposed AG approach. Furthermore, a comparison with existing state-of-the-art methods shows that the AG approach achieves the best results in terms of efficiency, robustness, safety, and smoothness.

Posted in: Robot motion planning , Tagged: ,

A robotic wheelchair navigation algorithm that plans paths taking into account the discomfort of the user

March 28, 2018 09:07 ,

Yoichi Morales, Atsushi Watanabe, Florent Ferreri, Jani Even, Kazuhiro Shinozawa, Norihiro Hagita, Passenger discomfort map for autonomous navigation in a robotic wheelchair, Robotics and Autonomous Systems, Volume 103, 2018, Pages 13-26, DOI: 10.1016/j.robot.2018.02.002.

This work presents a navigational approach that takes into consideration the perception of comfort by a human passenger. Comfort is the state of being at ease and free from stress; thus, comfortable navigation is a ride that, in addition to being safe, is perceived by the passenger as being free from anxiety and stress. This study considers how to compute passenger comfortable paths. To compute such paths, passenger discomfort is studied in locations with good visibility and those with no visibility. In locations with good visibility, passenger preference to ride in the road is studied. For locations with non-visible areas, the relationship between passenger visibility and discomfort is studied. Autonomous-navigation experiments are performed to build a map of human discomfort that is used to compute global paths. A path planner is proposed that minimizes a three-variable cost function: location discomfort cost, area visibility cost, and path length cost. Planner parameters are calibrated toward a composite trajectory histogram built with data taken from participant self-driving trajectories. Finally, autonomous navigation experiments with 30 participants show that the proposed approach is rated as more comfortable than the state-of-the-art shortest planner approach.

Posted in: Robot motion planning , Tagged: ,