Combining the A* Algorithm with Neural Networks to Solve the Team Orienteering Problem with Obstacles and Environmental Factors
Freixes, Alfons (Euncet Business School (Catalunya))
Panadero, Javier (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Juan, Ángel A (Universitat Politècnica de València. Centre de Recerca Gestió i Enginyeria de Producció)
Serrat, Carles (Universitat Politècnica de Catalunya. Departament de Matemàtiques)

Date:	2025
Abstract:	This paper addresses the team orienteering problem applied to unmanned aerial vehicles (UAVs), considering obstacle avoidance and environmental factors such as wind conditions and payload weight. The objective is to optimize UAV routes to maximize collected rewards while adhering to operational constraints. To achieve this, we employ a simheuristic algorithm for the overall route optimization, while integrating the A* algorithm to determine feasible paths between nodes that avoid obstacles in a 2D grid-based environment. Then, a feedforward neural network estimates travel time based on UAV speed, wind conditions, trajectory distance, and payload weight. This estimation is incorporated into the optimization process to improve route planning accuracy. Numerical experiments evaluate the impact of various parameters, including obstacle placement, UAV speed, wind conditions, and payload weight. These experiments include maps with 30 to 100 points of interest and varying obstacle densities and show that our hybrid method improves solution quality by up to (Formula presented. ) in total profit compared to a baseline approach. Furthermore, computation times remain within 5-10% of the baseline, showing that the added predictive layer maintains computational efficiency.
Grants:	Agencia Estatal de Investigación RED2022-134703-T Agencia Estatal de Investigación PID2022-138860NB-I00
Rights:	Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, la comunicació pública de l'obra i la creació d'obres derivades, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original.
Language:	Anglès
Document:	Article ; recerca ; Versió publicada
Subject:	A* algorithm ; Artificial intelligence ; Team orienteering problem ; Unmanned aerial vehicles
Published in:	Algorithms, Vol. 18, Issue 6 (June 2025) , art. 309, ISSN 1999-4893

DOI: 10.3390/a18060309

18 p, 1.4 MB

The record appears in these collections:
Articles > Research articles
Articles > Published articles