TY - GEN

T1 - Optimal Routing of Modular Agents on a Graph

AU - Jagdale, Karan

AU - Ornik, Melkior

N1 - Publisher Copyright:
© 2023 IEEE.

PY - 2023

Y1 - 2023

N2 - Motivated by an emerging framework of Autonomous Modular Vehicles, we consider the abstract problem of optimally routing two modules, i.e., vehicles that can attach to or detach from each other in motion on a graph. The modules' objective is to reach a preset set of nodes while incurring minimum resource costs. We assume that the resource cost incurred by an agent formed by joining two modules is the same as that of a single module. Such a cost formulation simplistically models the benefits of joining two modules, such as passenger redistribution between the modules, less traffic congestion, and higher fuel efficiency. To find an optimal plan, we propose a heuristic algorithm that uses the notion of graph centrality to determine when and where to join the modules. Additionally, we use the nearest neighbor approach to estimate the cost routing for joined or separated modules. Based on this estimated cost, the algorithm determines the subsequent nodes for both modules. The proposed algorithm is polynomial time: the worst-case number of calculations scale as the eighth power of the number of the total nodes in the graph. To validate its benefits, we simulate the proposed algorithm on a large number of pseudo-random graphs, motivated by real transportation scenario where it performs better than the most relevant benchmark, an adapted nearest neighbor algorithm for two separate agents, more than 85 percent of the time.

AB - Motivated by an emerging framework of Autonomous Modular Vehicles, we consider the abstract problem of optimally routing two modules, i.e., vehicles that can attach to or detach from each other in motion on a graph. The modules' objective is to reach a preset set of nodes while incurring minimum resource costs. We assume that the resource cost incurred by an agent formed by joining two modules is the same as that of a single module. Such a cost formulation simplistically models the benefits of joining two modules, such as passenger redistribution between the modules, less traffic congestion, and higher fuel efficiency. To find an optimal plan, we propose a heuristic algorithm that uses the notion of graph centrality to determine when and where to join the modules. Additionally, we use the nearest neighbor approach to estimate the cost routing for joined or separated modules. Based on this estimated cost, the algorithm determines the subsequent nodes for both modules. The proposed algorithm is polynomial time: the worst-case number of calculations scale as the eighth power of the number of the total nodes in the graph. To validate its benefits, we simulate the proposed algorithm on a large number of pseudo-random graphs, motivated by real transportation scenario where it performs better than the most relevant benchmark, an adapted nearest neighbor algorithm for two separate agents, more than 85 percent of the time.

UR - http://www.scopus.com/inward/record.url?scp=85167984410&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85167984410&partnerID=8YFLogxK

U2 - 10.1109/IV55152.2023.10186663

DO - 10.1109/IV55152.2023.10186663

M3 - Conference contribution

AN - SCOPUS:85167984410

T3 - IEEE Intelligent Vehicles Symposium, Proceedings

BT - IV 2023 - IEEE Intelligent Vehicles Symposium, Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 34th IEEE Intelligent Vehicles Symposium, IV 2023

Y2 - 4 June 2023 through 7 June 2023

ER -