MSc. Thesis Defense: Abdullah Alluş

Classical and Learning-Based Multi-Goal Ordering and Path Planning for Mobile Robots

Abdullah Alluş
Mechatronics Engineering, Master Thesis, 2025

Thesis Jury

Prof. Dr. Mustafa Ünel (Thesis Advisor)

Assoc. Prof. Dr. Kemalettin Erbatur

Assist. Prof. Dr. Ertuğrul Bayraktar

Date & Time: 16th July, 2025 – 10:00 AM

Place: FENS L065

Keywords : Mobile Robots, Path-Planning, Multi-Goal Pathfinding, A-Star, Transformers

Abstract

In the field of autonomous mobile robotics, efficient and scalable solutions to the multi-goal ordering and path planning problem—where a robot must visit a set of spatially distributed goal nodes in the most optimal sequence—remain a significant challenge. In this study, we develop two approaches to tackle this important problem. The first one is a classical geometry-based approach and the second one is a learning-based approach that addresses the problem using either a traditional machine learning technique or a transformer-based method.

In the classical approach, we propose a novel ordering strategy based on a one-distance-two-angles paradigm, which reduces reliance on traditional distance metrics by incorporating geometric considerations to infer optimal visiting sequences. This ordering procedure is paired with an improved version of the A* algorithm that integrates principles from computer graphics to eliminate redundant zigzags and intermediate points often present in grid-based environments, resulting in smoother and more cost-effective paths without compromising computational efficiency. Additionally, we introduce two learning-based frameworks to predict goal visiting orders. The first is a traditional machine learning model trained on hand-crafted features derived from brute-force optimal solutions, capturing geometric patterns such as distances, angles, and spatial relationships. The second is a transformer model trained on features extracted using CNNs and Relational Transformers, along with geometric context-based features from optimal paths. Our experiments demonstrate that both models generalise effectively to unseen environments and large-scale scenarios, achieving high accuracy in reproducing near-optimal orders.

We conducted extensive evaluations on a variety of publicly available datasets and synthetic environments, benchmarking our proposed approaches against state-of-the-art algorithms. Results demonstrate that both the classical and learning-based methods outperform existing solutions in terms of distance cost, path smoothness, and computational runtime. The proposed methods also show strong scalability and reproducibility across different problem instances.