Abstract
The chapter focuses upon the use of hybrid planning systems that are primarily behavioral in nature. Three approaches are discussed. In the first approach, the authors solve the problem of path planning using a combination of A* algorithm and Fuzzy Inference System. The A* algorithm does the higher-level planning by working on a lower detail map. The algorithm finds the shortest path, while at the same time generating the result in a finite time. The A* algorithm is used on a probability-based map. The lower-level planning is done by the Fuzzy Inference System (FIS). The FIS works on the detailed graph where the occurrence of obstacles is precisely known. The FIS generates paths that take into account the non-holonomic constraints and generate smoother paths. The results of A* algorithm serve as a guide for FIS planner. The FIS system is initially generated using rules from common sense. Once this model is ready, the fuzzy parameters are optimized by Genetic Algorithm (GA). The GA tries to optimize the distance from the closest obstacle, total path length, and the sharpest turn at any time in the journey of the robot. Many times, the planning algorithm may require a map breakup such that the coarser-level graph also has a high degree of resolution and A* algorithm may not be able to work. Hence, in the second approach, the authors replace the A* algorithm with GA. Both approaches were tested on various complex and simple paths. All paths generated were optimal in terms of path length and smoothness. Their last approach is based on dynamic programming, which, in this implementation, is similar to the use of neurons embedded in the map being planned. In this approach, the authors talk about the use of extra nodes in the planning framework called accelerating nodes. These nodes are less in number and fully interconnected. These nodes transmit information about any map change and blockages to each other for sudden re-planning to be initiated. These nodes further guide the robot until re-planning completes.
TopIntroduction
The problem of planning for mobile robot has multiple issues which planning algorithms need to solve as far as possible. The same is true with the behavioral planning approaches in which we chiefly studied the fuzzy and the neural approaches. These approaches model the behavior of the robot and make it move from one point to the other in the robotic map. The fuzzy approaches in particular are good for fast and real-time planning. They can work in dynamic maps as well as the generated paths and obey non-holonomic constraints. However, it is possible for the robot to get struck. The optimality of the path cannot be ascertained. These algorithms cannot maneuver maze-like maps by their modeling techniques. The various advantages and disadvantages are summarized in Table 1. The purpose of this chapter is to attempt to improve upon these techniques, making them better for planning for most scenarios.
Table 1. Advantages and disadvantages of fuzzy inference systems
| S. No. | Advantages | Disadvantages |
| 1. | Very less computational time. Real time performance | Not-complete. Can get struck in simple maps. |
| 2. | In base forms, works for dynamic maps and sudden obstacles | Cannot solve maze-like maps. There is no global level planning. |
| 3. | Validity of non-holonomic constraints | Not-optimal |
It the earlier chapters we dealt with the problem of planning by A* algorithm which was shown to generate good results in a variety of maps. However, the algorithm is computationally very expensive. In practical problems, the map may be too large for the standard A* algorithm to perform. Hence, the A* algorithm cannot be applied over the entire problem map. The A*algorithm also generates very sharp paths which the real robot would find it very difficult to follow. This is the case when the number of allowed moves is few and increasing them further increases the computational complexity drastically. The paths generated by the algorithm disobey the non-holonomic constraints of the robot. In this chapter, the aim is to adapt A* algorithm according to these constraints.
In hybridizing the solution, we have usually been making different algorithms run on maps at different resolutions or degree of abstraction. A manner of doing the same is to use probabilistic maps as discussed in chapter 7. In the discussed approach, the map is modeled in a way similar to the quad tree approach (Kambhampati & Davis, 1986). Here at the top, the nodes have a high degree of uncertainty regarding the presence or absence of the obstacles. This uncertainty is measured in terms of grayness of the cell. A completely white cell denotes the complete absence of obstacles from the complete region. On the other hand, full black color denotes the conformation of presence of obstacles in the cell. The grey denotes the intermediate values with the intensity denoting the probability of the cell being free from obstacles.