Common Planning Techniques

Introduction

Motion planning of mobile robots is a very interesting problem, which has a large number of issues associated with it. The choice between online and offline planner, degree of optimality of the path, complexity of the map, etc. play a major role in choosing the search algorithm or designing of a new algorithm. In many algorithms, the internal algorithm parameters may need to be tuned for better performance. The computational time and optimality of a path for most general graphs with no roadmap information may generally be contradictory to each other. The algorithms giving early results may not guarantee the optimality of the paths generated and vice versa.

Graph search methods are extensively used for motion planning, as we discussed in chapter 2. Here the task is to convert the given problem into a graph, and then to use any standard graph search technique for solving the problem. There are, however, many approaches that use similar modeling scenarios or a similar working methodology. The purpose of this chapter is to present these approaches and possibly analyze them for performance in various scenarios.

Motion planning deals with computation of a feasible path from a given source to a given goal. The robot must avoid all the possible static and dynamic obstacles on its way. We saw in chapter 2 that the graph modeling more or less assumed that each pixel be a vertex of the map. This enabled the conversion of a simple maze into a search graph. In general, we may have different nodes kept at different places of the map that help in the computation of the path from source to goal. This node based planning enables us to use the information processed by the various nodes, to get the optimal path. Here each node may denote a pixel, or a still higher area in case the complete map is of a high resolution.

The graph-based planning is a complete algorithm. Completeness of algorithm refers to the fact that a solution must be returned by the algorithm if it exists. The computational time for many cases may however be high. For these reasons graph based approaches are widely used for higher level planning where the complete problem at a very abstract level may be given to the algorithm to figure out a vague work plan. The other real-time planners may be used for making the exact plan to be physically traversed by the robot.

The choice of algorithm between online and offline planners is always hard. The real world with all its uncertainties advocates the use of online planners. This ensures that the robot would be able to escape any possible obstacle that might suddenly crop in. Dynamism is again a very common feature in any practical planning scenario where the multiple obstacles in form of other robots, humans, machines, etc. may be moving around the map. This further necessitates the planners being online.

However, the online planners can only perform limited computation and mostly make decisions based on the current surroundings. This may not ensure the overall path optimality or completeness. In most cases, the robot may not at all reach the goal, or may reach the goal in sub-optimal paths. The offline planners with some heavy computation do attempt to try as many combinations of paths as possible to figure out the most efficient path. For most of the scenarios where the optimal path of the robot is not very simple, or there is a possibility of multiple paths, these planners may perform a lot better. However, the scenario might change in the presence of uncertainties. The robot may make some computations, plan a path, and move as per the generated plan, only to find that the scenario in the meantime has changed and the plan is no longer valid. In such scenarios, this planning fails.

Autonomous vehicles are cars, which are not driven by a human driver, but the vehicle drives itself. These vehicles are a lot safer as the vehicles do not fatigue, and further, the combined view of multiple sensors is less prone to errors as compared to humans. In 2007, DARPA organized the DARPA Urban Challenge competition, which was a race between autonomous vehicles. The vehicle named Talos from MIT stood third in the contest. The vehicle’s success was largely due to the planning algorithm, which enabled the vehicle to avoid other vehicles and obstacles, at the same time staying within the road boundaries (Kuwata, 2009). The planning algorithm used by the team was Rapidly Exploring Random Trees, which is one of the topics of this chapter.