Self-Organizing Networks with Automatic Routing (SONAR) for Search and Rescue

Abstract

This is a MSc Thesis, summarizing the research conducted in the use of a bioinspired technique, namely Ant Algorithms (AA), as a path planning strategy in a 2D maze solving problem. The motivation behind the project is to optimize path planning for use in real life search problems, like Search and rescue Operation (SAR), in unknown arbitrary environment by a group of autonomous robotic agents. An added element of guidance in the form of a beacon signal from the target is introduced and studied. The search operation is limited to a time and energy constraint, considering the critical nature of its application. The AA decision making approach is modified to fit a 4 directional movement where decision needs to be taken at each step by individual agents. Five different variants of AA are developed by introducing a beacon oriented pheromone initialization, inverting the effect of pheromones, and lastly by extending the sensing range of the agents. Performance, in terms of number of steps needed to solve the maze is compared across all models, resulting in the algorithm with inverted pheromone effect (iAA) being the clear winner. The inverted (or repulsive) nature of the pheromone in iAA plays a crucial role in removing the clustering effect observed in AA and its versions, allowing better and faster exploration of the maze. The influence of the beacon in the simulation was counterintuitive due to the constant trapping of agents between adjoined obstacles because of the beacon pull. All models were tested across different maze sizes, and complexities. Parametric optimization was performed for the two independent variables in the AA and iAA probability equations: the pheromone bias (a) and the random bias (c). Lastly, the energy expenditure of the winner iAA algorithm, with weightedcosts assigned to movement types, was studied by varying group sizes for different mazes. The results achieved with iAA are promising and open new prospects of further optimizing path planning for the growth of AI in dynamic search scenarios.

Date of Award	Apr 2018
Original language	American English
Supervisor	Dymitr Ruta (Supervisor)