Topological Mapping in Swarm Robotics

Abstract

This PhD aims to explore different engineered ways a simulated robotic swarm can topologically map, explore, and localise in an environment. Core to developing and understanding the utility of robotic swarms is the need for a localisation and route planning capability, enabled by robust map generation. This PhD will develop synthetic environment models of robotic swarms supported by topological maps to enable localisation and navigation. Topological maps are a category of maps which hold distinctive data from conventional topographical maps. These maps, often represented as graphs, can be considerably more practical for machines to understand while being smaller to store in memory. There are multiple challenges in generating the topological maps, including the task of loop closure, map fusion (from separate swarm members), and ensuring the ability to provide a complete map view. Consequently, throughout the project, challenges such as graph operation optimisation and swarm control are investigated. Topological maps can be more practical for machines to use for navigation purposes as the information stored is in a format that can be directly used by path planning algorithms. This however potentially assumes higher levels of navigation capabilities from the robots. Such maps are also inherently more scalable as adding new vertices or edges is trivial compared to expanding a bitmap (the traditional representation of topographical maps). Equivalently, removing or altering a vertex or edge is a relatively cheap and simple operation. In the context of this project, path intersections are represented as vertices and their connecting paths as edges. Objective metadata on the environment will also be stored to be used to recognise one intersection from another. This metadata includes the relative outgoing bearings of junctions encapsulated in vertices, and path length / terrain type encapsulated in edges. All this data can be evaluated without the use of any universal navigation techniques such as GPS, bearing compasses, or uniquely identifiable landmarks. Swarm robotics is a bio-inspired field which focuses on relatively simple, yet scalable systems exhibiting distributed control and maintaining strictly local interaction. The goal is to be able to release a swarm into an environment and have it cooperatively and simultaneously build a topological map that members of the swarm can then localise in and traverse around. This map can be extracted from the swarm at any time to be usable to outside systems. Sensor noise and inaccurate environment readings cause inevitable mistakes while interpreting the environment. Consequently, ongoing peer review and pruning of collected data is an essential component of the mapping process. Symmetry and aliasing related issues are tackled through neighbourhood checking. Finally, a quadtree data structure is employed for optimising graph operations such as searching and matching. As maps become larger and more complex, it is important to develop strategies that avoid exhaustive iterations over all nodes. Each node is first mapped to a Cartesian search space based on its properties, and each area of the Cartesian space is mapped to a leaf in the quadtree. As similar nodes will be mapped to the same tree leaf, all similar nodes can be checked simply by only iterating over a single containing leaf. This yields a faster than linear (O(n)) time complexity of O(s + d), where s is the maximum number of vertices associated to a tree leaf, and d is the depth of the tree. Finding solutions to swarm topological mapping can be advantageous in situations where dangerous environments need to be quickly searched or surveyed, including survivor rescue in disaster areas or path planning in changing hazardous environments. The proposed approach has been shown to be viable, even in the presence of high amounts of unknown noise added to the sensory readings. The interactions between agents do propagate map knowledge through the swarm and we have shown that the swarm can be controlled to explore in different ways, including being directed by an external entity.

Date of Award	2022
Original language	English
Awarding Institution	Aberystwyth University
Supervisor	Fred Labrosse (Supervisor) & Myra Wilson (Supervisor)