Multi-Goal Path Planning in Cluttered Environments with PRM-Guided Self-Organising Maps

We consider the problem of multi-robot, multi-goal path planning in cluttered environments, motivated by scenarios including surveillance, object search, and package delivery in crowded office spaces and urban environments. While many solutions have been proposed for related vehicle routing problems, they typically do not generalise well for cluttered environments with obstacles due to the introduction of non-Euclidean point-to-point distances. We consider a Self-Organising Map (SOM) algorithm due to its versatility in optimising waypoints within region-based goals. Since standard SOM heavily relies on Euclidean distance-based operations, we propose a generalised SOM with several new innovations: Probabilistic Roadmap (PRM)-guided adaptation and winner selection rules, a two-level path representation for effective routing between goals, and caching operations to overcome the increased computational demands. We present simulation experiments in office and maze environments with one to three robots that show that our approach significantly outperforms standard SOM algorithms as it explicitly reasons over collision avoidance. These results demonstrate the viability of our PRM-guided SOM algorithm for tasks including surveillance in cluttered environments.