Category Archives: Robot Motion Planning

A comparison / evaluation of bug algorithms for mobile robots and their bad performance when relying in only one sensor

K.N. McGuire, G.C.H.E. de Croon, K. Tuyls, A comparative study of bug algorithms for robot navigation,. Robotics and Autonomous Systems, Volume 121, DOI: 10.1016/j.robot.2019.103261.

This paper presents a literature survey and a comparative study of Bug Algorithms, with the goal of investigating their potential for robotic navigation. At first sight, these methods seem to provide an efficient navigation paradigm, ideal for implementations on tiny robots with limited resources. Closer inspection, however, shows that many of these Bug Algorithms assume perfect global position estimate of the robot which in GPS-denied environments implies considerable expenses of computation and memory — relying on accurate Simultaneous Localization And Mapping (SLAM) or Visual Odometry (VO) methods. We compare a selection of Bug Algorithms in a simulated robot and environment where they endure different types noise and failure-cases of their on-board sensors. From the simulation results, we conclude that the implemented Bug Algorithms’ performances are sensitive to many types of sensor-noise, which was most noticeable for odometry-drift. This raises the question if Bug Algorithms are suitable for real-world, on-board, robotic navigation as is. Variations that use multiple sensors to keep track of their progress towards the goal, were more adept in completing their task in the presence of sensor-failures. This shows that Bug Algorithms must spread their risk, by relying on the readings of multiple sensors, to be suitable for real-world deployment.

Analyzing effects of loads and terrain on wheel shapes in order to reduce errors in position estimation of a mobile wheeled robot

Smieszek, M., Dobrzanska, M. & Dobrzanski, P. , The impact of load on the wheel rolling radius and slip in a small mobile platform. Auton Robot (2019) 43: 2095, DOI: 10.1007/s10514-019-09857-0.

Automated guided vehicles are used in a variety of applications. Their major purpose is to replace humans in onerous, monotonous and sometimes dangerous operations. Such vehicles are controlled and navigated by application-specific software. In the case of vehicles used in multiple environments and operating conditions, such as the vehicles which are the subject of this study, a reasonable approach is required when selecting the navigation system. The vehicle may travel around an enclosed hall and around an open yard. The pavement surface may be smooth or uneven. Vehicle wheels should be flexible and facilitate the isolation and absorption of vibrations in order to reduce the effect of surface unevenness to the load. Another important factor affecting the operating conditions are changes to vehicle load resulting from the distribution of the load and the weight carried. Considering all of the factors previously mentioned, the vehicle’s navigation and control system is required to meet two opposing criteria. One of them is low price and simplicity, the other is ensuring the required accuracy when following the preset route. In the course of this study, a methodology was developed and tested which aims to obtain a satisfactory compromise between those two conflicting criteria. During the study a vehicle made in Technical University of Rzeszow was used. The results of the experimental research have been analysed. The results of the analysis provided a foundation for the development of a methodology leading to a reduction in navigation errors. Movement simulations for the proposed vehicle system demonstrated the potential for a significant reduction in the number of positioning errors.

Hardware efficient collision avoidance for mobile robots through the use of interval arithmetics and parallelism

Pranjal Vyas, Leena Vachhani, K Sridharan, Hardware-efficient interval analysis based collision detection and avoidance for mobile robots. Mechatronics, Volume 62, 2019, DOI: 10.1016/j.mechatronics.2019.102258.

Collision detection and avoidance is challenging when the mobile robot is moving among multiple dynamic obstacles. A hardware-efficient architecture supporting parallel implementation is presented in this work for low-power, faster and reliable collision-free motion planning. An approach based on interval analysis is developed for designing an efficient hardware architecture. The proposed architecture achieves parallelism which can be combined with any robotic task involving multiple obstacles. Interval arithmetic is used for representing the pose of the robot and the obstacle as velocity intervals in a fixed time period. These intervals correspond to sub-intervals such as arcs and line-segments. In particular, the collision detection problem for dynamic objects involves the computation of line segment-arc intersections and segment-segment intersections. The intersection of these boundary curves is carried out in a hardware-efficient manner so that it avoids complex arithmetic computations such as multiplication, division etc and exploits parallelism. We develop several results on intersection of these sub-intervals for collision detection and use them to obtain a hardware-efficient collision detection algorithm that requires only shift and add-type of computations. The algorithm is further used in developing a hardware-efficient technique for finding an exhaustive set of solutions for avoiding collision of the robot with dynamic obstacles. Simulation results in MatLab and experiments with a Field Programmable Gate Array (FPGA)-based robot show that a variety of collision avoidance techniques can be implemented using the proposed solution set that guarantees collision avoidance with multiple obstacles.

A related work with a nice taxonomy of robot navigation algorithms

Eduardo J. Molinos, Ángel Llamazares, Manuel Ocaña Dynamic window based approaches for avoiding obstacles in moving, Robotics and Autonomous Systems,
Volume 118, 2019, Pages 112-130 DOI: 10.1016/j.robot.2019.05.003.

In recent years, Unmanned Ground Vehicles (UGVs) have been widely used as service robots. Unlike industrial robots, which are situated in fixed and controlled positions, UGVs work in dynamic environments, sharing the environment with other vehicles and humans. These robots should be able to move without colliding with any obstacle, assuring its integrity and the environment safety. In this paper, we propose two adaptations of the classical Dynamic Window algorithm for dealing with dynamic obstacles like Dynamic Window for Dynamic Obstacles (DW4DO) and Dynamic Window for Dynamic Obstacles Tree (DW4DOT). These new algorithms are compared with our previous algorithms based on Curvature Velocity Methods: Predicted Curvature Velocity Method (PCVM) and Dynamic Curvature Velocity Method (DCVM). Proposals have been validated in both simulated and real environment using several robotic platforms.

A novel path planning method for both global and local planning with provable behavior, and a nice survey of existing navigation methods

Sgorbissa, A., Integrated robot planning, path following, and obstacle avoidance in two and three dimensions: wheeled robots, underwater vehicles, and multicopters, The International Journal of Robotics Research, DOI: 10.1177/0278364919846910.

We propose an innovative, integrated solution to path planning, path following, and obstacle avoidance that is suitable both for 2D and 3D navigation. The proposed method takes as input a generic curve connecting a start and a goal position, and is able to find a corresponding path from start to goal in a maze-like environment even in the absence of global information, it guarantees convergence to the path with kinematic control, and finally avoids locally sensed obstacles without becoming trapped in deadlocks. This is achieved by computing a closed-form expression in which the control variables are a continuous function of the input curve, the robot’s state, and the distance of all the locally sensed obstacles. Specifically, we introduce a novel formalism for describing the path in two and three dimensions, as well as a computationally efficient method for path deformation (based only on local sensor readings) that is able to find a path to the goal even when such path cannot be produced through continuous deformations of the original. The article provides formal proofs of all the properties above, as well as simulated results in a simulated environment with a wheeled robot, an underwater vehicle, and a multicopter.

Improving on-line Monte Carlo POMDP (DESTOP in particular) in discrete spaces through the use of importance sampling, and a nice summary of the problem and of current on-line POMDP approaches

Luo, Y., Bai, H., Hsu, D., & Lee, W. S., Importance sampling for online planning under uncertainty, The International Journal of Robotics Research, 38(2–3), 162–181, 2019 DOI: 10.1177/0278364918780322.

The partially observable Markov decision process (POMDP) provides a principled general framework for robot planning under uncertainty. Leveraging the idea of Monte Carlo sampling, recent POMDP planning algorithms have scaled up to various challenging robotic tasks, including, real-time online planning for autonomous vehicles. To further improve online planning performance, this paper presents IS-DESPOT, which introduces importance sampling to DESPOT, a state-of-the-art sampling-based POMDP algorithm for planning under uncertainty. Importance sampling improves DESPOT’s performance when there are critical, but rare events, which are difficult to sample. We prove that IS-DESPOT retains the theoretical guarantee of DESPOT. We demonstrate empirically that importance sampling significantly improves the performance of online POMDP planning for suitable tasks. We also present a general method for learning the importance sampling distribution.

RL and Inverse RL based on MDPs for autonomous vehicles, and a nice historical review of the topic of a.v.

Changxi You, Jianbo Lu, Dimitar Filev, Panagiotis Tsiotras, Advanced planning for autonomous vehicles using reinforcement learning and deep inverse reinforcement learning, Robotics and Autonomous Systems, Volume 114, 2019, Pages 1-18 DOI: 10.1016/j.robot.2019.01.003.

Autonomous vehicles promise to improve traffic safety while, at the same time, increase fuel efficiency and reduce congestion. They represent the main trend in future intelligent transportation systems. This paper concentrates on the planning problem of autonomous vehicles in traffic. We model the interaction between the autonomous vehicle and the environment as a stochastic Markov decision process (MDP) and consider the driving style of an expert driver as the target to be learned. The road geometry is taken into consideration in the MDP model in order to incorporate more diverse driving styles. The desired, expert-like driving behavior of the autonomous vehicle is obtained as follows: First, we design the reward function of the corresponding MDP and determine the optimal driving strategy for the autonomous vehicle using reinforcement learning techniques. Second, we collect a number of demonstrations from an expert driver and learn the optimal driving strategy based on data using inverse reinforcement learning. The unknown reward function of the expert driver is approximated using a deep neural-network (DNN). We clarify and validate the application of the maximum entropy principle (MEP) to learn the DNN reward function, and provide the necessary derivations for using the maximum entropy principle to learn a parameterized feature (reward) function. Simulated results demonstrate the desired driving behaviors of an autonomous vehicle using both the reinforcement learning and inverse reinforcement learning techniques.

An application of MDPs to UAV collision-free navigation with an interesting taxonomy of the state-of-the-art

Xiang Yu1, Xiaobin Zhou2, Youmin Zhang, Collision-Free Trajectory Generation and Tracking for UAVs Using Markov Decision Process in a Cluttered Environment, Journal of Intelligent & Robotic Systems, 2019, 93:17–32 DOI: 10.1007/s10846-018-0802-z.

A collision-free trajectory generation and tracking method capable of re-planning unmanned aerial vehicle (UAV) trajectories can increase flight safety and decrease the possibility of mission failures. In this paper, a Markov decision process (MDP) based algorithm combined with backtracking method is presented to create a safe trajectory in the case of hostile environments. Subsequently, a differential flatness method is adopted to smooth the profile of the rerouted trajectory for satisfying the UAV physical constraints. Lastly, a flight controller based on passivity-based control (PBC) is designed to maintain UAV’s stability and trajectory tracking performance. simulation results demonstrate that the UAV with the proposed strategy is capable of avoiding obstacles in a hostile environment.

A novel paradigm for motion planning based on probabilistic inference

Mukadam, M., Dong, J., Yan, X., Dellaert, F., & Boots, B. , Continuous-time Gaussian process motion planning via probabilistic inference, The International Journal of Robotics Research, 37(11), 1319–1340, DOI: 10.1177/0278364918790369.

We introduce a novel formulation of motion planning, for continuous-time trajectories, as probabilistic inference. We first show how smooth continuous-time trajectories can be represented by a small number of states using sparse Gaussian process (GP) models. We next develop an efficient gradient-based optimization algorithm that exploits this sparsity and GP interpolation. We call this algorithm the Gaussian Process Motion Planner (GPMP). We then detail how motion planning problems can be formulated as probabilistic inference on a factor graph. This forms the basis for GPMP2, a very efficient algorithm that combines GP representations of trajectories with fast, structure-exploiting inference via numerical optimization. Finally, we extend GPMP2 to an incremental algorithm, iGPMP2, that can efficiently replan when conditions change. We benchmark our algorithms against several sampling-based and trajectory optimization-based motion planning algorithms on planning problems in multiple environments. Our evaluation reveals that GPMP2 is several times faster than previous algorithms while retaining robustness. We also benchmark iGPMP2 on replanning problems, and show that it can find successful solutions in a fraction of the time required by GPMP2 to replan from scratch.

On the need to replanning in POMDPs when applied to real systems, due to imperfect sensing and computational cost of online planning

Ali-akbar Agha-mohammadi et al., SLAP: Simultaneous Localization and Planning Under Uncertainty via Dynamic Replanning in Belief Space, IEEE Transactions on Robotics, vol. 34, no. 5, DOI: 10.1109/TRO.2018.2838556.

Simultaneous localization and planning (SLAP) is a crucial ability for an autonomous robot operating under uncertainty. In its most general form, SLAP induces a continuous partially observable Markov decision process (POMDP), which needs to be repeatedly solved online. This paper addresses this problem and proposes a dynamic replanning scheme in belief space. The underlying POMDP, which is continuous in state, action, and observation space, is approximated offline via sampling-based methods, but operates in a replanning loop online to admit local improvements to the coarse offline policy. This construct enables the proposed method to combat changing environments and large localization errors, even when the change alters the homotopy class of the optimal trajectory. It further outperforms the state-of-the-art Feedback-based Information RoadMap (FIRM) method by eliminating unnecessary stabilization steps. Applying belief space planning to physical systems brings with it a plethora of challenges. A key focus of this paper is to implement the proposed planner on a physical robot and show the SLAP solution performance under uncertainty, in changing environments and in the presence of large disturbances, such as a kidnapped robot situation.