On the use of optimal search algorithms with artificial potential field for robot soccer navigation : Computer Science, Master of Science - Dong, Chen (Massey University, 2018)
The artificial potential field (APF) is a popular method of choice for robot navigation, as it offers an intuitive model clearly defining all attractive and repulsive forces acting on the robot [3] [25] [29] [43] [50]. However, there are drawbacks that limit the usage of this method. For instance, the local minima problem that gets a robot trapped, and the Goal-Non-Reachable-with-Obstacle-Nearby (GNRON) problem, as reported in [51] [5] [23] [2] and [3]. In order to avoid these limitations, this research focuses on devising a methodology of combining the artificial potential field with a selection of optimal search algorithms. This work investigates the performance of the method when using different optimal search algorithms such as the A* algorithm and the any-angle path-planning Theta* Search, in combination with different types of artifcial potential field generators. We also present a novel integration technique, whereby the Potential Field approach is utilized as an internal component of an optimal search algorithm, considering the safeness of the calculated paths. Furthermore, this study also explores the optimization of several auxiliary algorithms used in conjunction with the APF-Optimal search integration: There are three different methods proposed for implementing the line-of-sight (LOS) component of the Theta* search, namely the simple line-of-sight checking algorithm, the modified Bresenham's line algorithm and the modified Cohen-Sutherland algorithm. Contrary to the studies presented in [5], [42], [48] and [40] where the APF and the optimal search algorithms were used separately, in this research, an integrative methodology involving the APF inside the optimal search with a newly proposed Safety Factor (SF) is explored. Experiment results indicate that the APF-A* Search with the SF can reduce the number of state expansions and therefore also the running time up to 19.61%, while maintaining the safeness of the path, as compared to APF-A* when not using the SF. Furthermore, this research also explores how the proposed hybrid algorithms can be used in developing multi-objective behaviours of single robot. In this regard, a robot soccer simulation platform with a physics engine is developed as well to support the exploration. Lastly, the performance of the proposed algorithms is examined under varying environment conditions. Evidences are provided showing that the method can be used in constructing the intelligence for a robot goal keeper and a robot attacker (ball shooter). A multitude of AI robot behaviours using the proposed methods are integrated via a finite state machine including: defensive positioning/parking, ball kicking/shooting, and target pursuing behaviours. Keywords : Artificial Potential Field, Optimal Searches, Robot Navigation, Multi- objective Behaviours.
Keywords: Artificial potential field; Optimal searches; Robot navigation; Multi-objective behaviours; Mobile robots; Automatic control; Computer algorithms; Soccer; Computer Simulation; Research Subject Categories::TECHNOLOGY::Information technology::Computer science