In this chapter, recent near-shortest path-planning algorithms with O(nlog n) in the quadric plane based on the Delaunay triangulation, Ahuja-Dijkstra algorithm, and ridge points are reviewed. The shortest path planning in the general three-dimensional situation is an NP-hard problem. The optimal solution can be approached under the assumption that the number of Steiner points is infinite. The state-the-art method has at most 2.81% difference on the shortest path length, but the computation time is 4216 times faster. Compared to the other O(nlog n) time near-shortest path approach (Kanai and Suzuki, KS’s algorithm), the path length of the Delaunay triangulation method is 0.28% longer than the KS’s algorithm with three Steiner points, but the computation is about 31.71 times faster. This, however, has only a few path length differences, which promises a good result, but the best computing time. Notably, these methods based on Delaunay triangulation concept are ideal for being extended to solve the path-planning problem on the Quadric surface or even the cruise missile mission planning and Mars rover.
Part of the book: Advanced Path Planning for Mobile Entities
Biologically inspired intelligence technique, an important embranchment of series on computational intelligence, plays a crucial role for robotics. The autonomous robot and vehicle industry has had an immense impact on our economy and society and this trend will continue with biologically inspired neural network techniques. In this chapter, multiple robots cooperate to achieve a common coverage goal efficiently, which can improve the work capacity, share the coverage tasks, and reduce the completion time by a biologically inspired intelligence technique, is addressed. In many real-world applications, the coverage task has to be completed without any prior knowledge of the environment. In this chapter, a neural dynamics approach is proposed for complete area coverage by multiple robots. A bio-inspired neural network is designed to model the dynamic environment and to guide a team of robots for the coverage task. The dynamics of each neuron in the topologically organized neural network is characterized by a shunting neural equation. Each mobile robot treats the other robots as moving obstacles. Each robot path is autonomously generated from the dynamic activity landscape of the neural network and the previous robot position. The proposed model algorithm is computationally simple. The feasibility is validated by four simulation studies.
Part of the book: Artificial Intelligence