The basic methods of planning for the mobile robot were the point of discussion in the previous few chapters. In each method, the authors observed that there were some advantages and some disadvantages. The disadvantages of the method restricted their use. In this chapter, the authors explore the possibilities of hybridizing different methods to solve the same problem, such that the advantages are added up and the disadvantages are eliminated as much as possible. They study two methods, which have their bases in graph techniques, in this chapter. In the first part, the authors make use of the Multi Neuron Heuristic Search (MNHS) algorithm. The algorithm is implemented in a hierarchical manner, where each generation of the algorithm gives a more detailed path that has a higher reaching probability. The map used for this purpose is based on a probabilistic approach where they measure the probability of collision with an obstacle while traveling inside the cell. As cells decompose, the cell size reduces and the probability starts to touch 0 or 1, depending upon the presence or absence of obstacles in the cell. In this approach, it is not compulsory to run the entire algorithm. One may rather break after a certain degree of certainty has been achieved. In the second approach, the authors hybridize the MNHS algorithm and Evolutionary Algorithms (EA). MNHS is slow but gives good paths for problems, with the added advantages of ensuring completeness. On the other hand, the EA gives results in finite time, but the optimality or completeness cannot be guaranteed. Here, the authors propose to mix these two techniques to get the added benefits of both these algorithms. The MNHS improves the performance of the algorithm while the EA does the task of time optimization in case of complex graphs. The EA carries forward the task of selection of points in the robotic map. These points are checked for feasibility and then converted into a traversable graph. The same is used by MNHS to find the optimal path from source to destination. In this way, the algorithm finds the best path without robotic collision.
TopIntroduction
There exist a significantly large number of algorithms used for solving the problem of robotic motion planning. Many of these algorithms were discussed in the previous chapters. Each of the algorithms had its own way of modeling the problem and then solving it. This made the individual algorithms have a number of advantages and a number of disadvantages. The advantages enabled the solutions return results to the problem, whereas the disadvantages implied some assumptions that must hold in the problem for the algorithm to find a result. The reason all the algorithms seemed to give fairly good results to the presented map was the fact that the input map had all the assumptions holding good in which the algorithms give results. As for example, we never gave a high-resolution map as the input to the graph-based search algorithm. Similarly, we never gave a map to an evolutionary algorithm that had a maze-like structure or a narrow corridor that make the resultant solution. If given as input, these algorithms would have completely failed, exposing the limitations of the individual algorithms.
Since limitations exist in all the algorithms of the study, it is important to formulate any mechanism to minimize the assumptions. In reality, we need an algorithm that computes very fast, gives results in real time, works for all kinds of obstacles including maze and narrow corridor, works with a high resolution map, etc. However, in reality no single algorithm may be able to cater to all the needs; hence, an attempt needs to be given to reduce as many limitations as possible, to as high a degree as possible. Humans are extremely good in solving maps, or puzzles as an analogy, and figuring out paths in all means. Humans can adapt rapidly to the type of scenario and adjust themselves automatically. In order to make the machines have this capability, or party have the capability, we cannot stick to a single algorithm.
We start with the task of selecting an algorithm and to attempt to reduce as many problems associated with the algorithm, as possible. This should lead to increased use of the algorithm, with maybe some added assumptions, which are more realistic. The task is hone by hybridizing the algorithms with other algorithms. This must be done in a manner that leads to increased advantages of both the algorithms and reduced disadvantages. Coupling two individual algorithms in any architecture must lead to better performances as the individual algorithms. This leads to a wide range of possibilities where we can attempt to mix any algorithm with any other algorithm or itself and study the resultant system. Some of the different possibilities would be discussed in this chapter and chapters to come.
Almost any algorithm can be fused with any other algorithm or even itself. This gives a fascinating playground to work with. The manner of hybridizing the maps is important to understand. A large number of models may be made that make use of multiple algorithms to solve the problem. It is not necessary that every two algorithms hybrid each other, but a large number of algorithms can be used for hybridization with each other. Even an algorithm can be fused with itself to create altogether a different algorithm. Some of these methods would be seen in this chapter and the couple of chapters to come.
We broadly present three fundamental techniques of hybridization of algorithms for problem solving. In the first technique, the map is broken down into multiple levels. Each of the levels has a different resolution (as we shall see later in this chapter). Different levels have different resolutions and hence difference computation times and demands for solving at the particular level. We may have different algorithms (or different instances of same algorithm) working at different levels or resolutions of the map. In this manner, the entire problem may be solved. An intelligent breakup technique may be used. All methods of hybridization we study in this book will fall under this category.
The second category is when the algorithms may work parallel to each other with different algorithms (or different instances of the same problem) working over different parts of the map. Hence, the entire map is broken down into regions. Each region has its own algorithm, which is only concerned with the problem of generating a path within that region. The results may be combined by some integration technique.