Category Archives: Robot Motion Planning

Study of how a complex motion planning problem solved through RRT can benefit from parallelization

November 12, 2015 19:59 ,

Brian W. Satzinger, Chelsea Lau, Marten Byl, Katie Byl, Tractable locomotion planning for RoboSimian, The International Journal of Robotics Research November 2015 vol. 34 no. 13 1541-1558, DOI: 10.1177/0278364915584947.

This paper investigates practical solutions for low-bandwidth, teleoperated mobility for RoboSimian in complex environments. Locomotion planning for this robot is challenging due to kinematic redundancy. We present an end-to-end planning method that exploits a reduced-dimension rapidly-exploring random tree search, constraining a subset of limbs to an inverse kinematics table. Then, we evaluate the performance of this approach through simulations in randomized environments and in the style of the Defense Advanced Research Projects Agency Robotics Challenges terrain both in simulation and with hardware.
We also illustrate the importance of allowing for significant body motion during swing leg motions on extreme terrain and quantify the trade-offs between computation time and execution time, subject to velocity and acceleration limits of the joints. These results lead us to hypothesize that appropriate statistical “investment” of parallel computing resources between competing formulations or flavors of random planning algorithms can improve motion planning performance significantly. Motivated by the need to improve the speed of limbed mobility for the Defense Advanced Research Projects Agency Robotics Challenge, we introduce one formulation of this resource allocation problem as a toy example and discuss advantages and implications of such trajectory planning for tractable locomotion on complex terrain.

Posted in: Robot motion planning , Tagged: ,

Automatic synthetis of controllers for robotic tasks from the specification of state-machine-like missions, nonlinear models of the robot and a representation of the robot workspace

March 11, 2015 11:52 ,

Jonathan A. DeCastro and Hadas Kress-Gazit, 2015, Synthesis of nonlinear continuous controllers for verifiably correct high-level, reactive behaviors, The International Journal of Robotics Research, 34: 378-394, DOI: 10.1177/0278364914557736.

Planning robotic missions in environments shared by humans involves designing controllers that are reactive to the environment yet able to fulfill a complex high-level task. This paper introduces a new method for designing low-level controllers for nonlinear robotic platforms based on a discrete-state high-level controller encoding the behaviors of a reactive task specification. We build our method upon a new type of trajectory constraint which we introduce in this paper, reactive composition, to provide the guarantee that any high-level reactive behavior may be fulfilled at any moment during the continuous execution. We generate pre-computed motion controllers in a piecewise manner by adopting a sample-based synthesis method that associates a certificate of invariance with each controller in the sample set. As a demonstration of our approach, we simulate different robotic platforms executing complex tasks in a variety of environments.

Posted in: Robot motion planning

A new simple method for mobile robot path planning based on particles and inspired in bacteria

December 19, 2014 10:24 ,

Md. Arafat Hossain, Israt Ferdous, Autonomous robot path planning in dynamic environment using a new optimization technique inspired by bacterial foraging technique, Robotics and Autonomous Systems, Volume 64, February 2015, Pages 137-141, ISSN 0921-8890, DOI: 10.1016/j.robot.2014.07.002

.

Path planning is one of the basic and interesting functions for a mobile robot. This paper explores the application of Bacterial Foraging Optimization to the problem of mobile robot navigation to determine the shortest feasible path to move from any current position to the target position in an unknown environment with moving obstacles. It develops a new algorithm based on Bacterial Foraging Optimization (BFO) technique. This algorithm finds a path towards the target and avoiding the obstacles using particles which are randomly distributed on a circle around a robot. The criterion on which it selects the best particle is the distance to the target and the Gaussian cost function of the particle. Then, a high level decision strategy is used for the selection and thus proceeds for the result. It works on local environment by using a simple robot sensor. So, it is free from having generated additional map which adds cost. Furthermore, it can be implemented without requirement to tuning algorithm and complex calculation. To simulate the algorithm, the program is written in C language and the environment is created by OpenGL. To test the efficiency of the proposed technique, results are compared with Basic Bacterial Foraging Optimization (BFO) and another well-known algorithm called Particle Swarm Optimization (PSO) to give the guarantee that the proposed method gives better and optimal path.

Posted in: Robot motion planning , Tagged: ,

Taking into account the way a path serves to avoid obstacles in order to improve the three main methods of robot path planning: graph-search, probabilistic and bug

December 19, 2014 10:17 ,

Emili Hernandez, Marc Carreras, Pere Ridao, A comparison of homotopic path planning algorithms for robotic applications , Robotics and Autonomous Systems, Volume 64, February 2015, Pages 44-58, ISSN 0921-8890, DOI: 10.1016/j.robot.2014.10.021

.

This paper addresses the path planning problem for robotic applications using homotopy classes. These classes provide a topological description of how paths avoid obstacles, which is an added value to the path planning problem. Homotopy classes are generated and sorted according to a lower bound heuristic estimator using a method we developed. Then, the classes are used to constrain and guide path planning algorithms. Three different path planners are presented and compared: a graph-search algorithm called Homotopic A∗ (HA∗), a probabilistic sample-based algorithm called Homotopic RRT (HRRT), and a bug-based algorithm called Homotopic Bug (HBug). Our method has been tested in simulation and in an underwater bathymetric map to compute the trajectory of an Autonomous Underwater Vehicle (AUV). A comparison with well-known path planning algorithms has also been included. Results show that our homotopic path planners improve the quality of the solutions of their respective non-homotopic versions with similar computation time while keeping the topological constraints.

Posted in: Robot motion planning , Tagged:

A good summary and classification of state-of-the-art motion planning algorithms and proposal of a new one that improve the expected computational cost

December 9, 2014 17:23 ,

Rickert, M.; Sieverling, A.; Brock, O., Balancing Exploration and Exploitation in Sampling-Based Motion Planning, Robotics, IEEE Transactions on , vol.30, no.6, pp.1305,1317, Dec. 2014. DOI: 10.1109/TRO.2014.2340191

We present the exploring/exploiting tree (EET) algorithm for motion planning. The EET planner deliberately trades probabilistic completeness for computational efficiency. This tradeoff enables the EET planner to outperform state-of-the-art sampling-based planners by up to three orders of magnitude. We show that these considerable speedups apply for a variety of challenging real-world motion planning problems. The performance improvements are achieved by leveraging work space information to continuously adjust the sampling behavior of the planner. When the available information captures the planning problem’s inherent structure, the planner’s sampler becomes increasingly exploitative. When the available information is less accurate, the planner automatically compensates by increasing local configuration space exploration. We show that active balancing of exploration and exploitation based on workspace information can be a key ingredient to enabling highly efficient motion planning in practical scenarios.

Posted in: Robot motion planning , Tagged: , ,