Robots have come a long way since first being introduced. They have evolved from machinery merely repeating the same action in factories, to human-like bodies, advanced cars without drivers and much more. This progress was mainly possible as a direct result of the continuous development of artificial intelligence (AI).
An autonomous mobile robot can traverse an environment without the need for human interference. This is achieved by using path-planning and obstacle-avoidance techniques. So-called traditional techniques include artificial potential field, cellular decomposition and Vector Field Histograms. However, the last twenty years have witnessed more cutting-edge approaches using AI techniques, including A*, fuzzy logic, rapidly-exploring random trees and ant colony optimisation.
In this project, two different heuristic algorithms were implemented in order to determine which would be the more suitable as a path- planning and obstacle-avoidance technique for dynamic environments. The first algorithm applied was a search-based algorithm referred to as Hybrid A* [1]. Search-based algorithms operate by first converting the given environment into a grid. Hybrid A* first uses the same technique as the A* algorithm to find a path using the knowledge it has of the environment. Furthermore, Hybrid A* would also simplify the path for the robot due to its movement constraints. The second algorithm was a sampling-based algorithm referred to as rapidly-exploring random tree* [2]. This algorithm would create a tree by randomly generating nodes around the free space of the environment, until it reaches the goal.
The two algorithms were tested in three different environments, as follows: a) without obstacles, b) with static obstacles, and c) with dynamic obstacles. In all tests, both algorithms successfully guided the robot around the static and dynamic obstacles without any collision. Moreover, it was observed that Hybrid A* algorithms always managed to find the shorter path in all tests. On the other hand, rapidly-exploring random tree* algorithms always required less average RAM and CPU usage for the static tests performed.
algorithm
[1] D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel, “Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments,” The International Journal of Robotics Research, vol. 29, no. 5, pp. 485–501, Apr. 2010, publisher: SAGE Publications Ltd STM.
[2] I. Noreen, A. Khan, and Z. Habib, “Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions,” International Journal of Advanced Computer Science and Applications, vol. 7, Nov. 2016.
Student: Sean Farrugia
Course: B.Sc. IT (Hons.) Artificial Intelligence
Supervisor: Dr Ingrid Vella