Planning in modular multi-agent systems

This work broadly focuses on planning in modular multi-agent systems where agents can attach and detach with each other to perform some task cooperatively, exploiting the benefits of their modularity. We utilize modularity and cast the problem statement at two different types of systems. Firstly, we develop an optimal policy to route modular agents on a graph. Secondly, we study the modular bus system where two buses can attach and detach when present at a stop and develop an optimal policy to reduce the average passenger travel time using their modularity. Apart from this, our work also includes developing strategies to predict the target of an agent using its partial and imperfect trajectory. In the first application of modular agent planning, we consider the abstract problem of optimally routing multiple modules, i.e., vehicles that can attach to or detach from each other in motion on a graph. The modules aim 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 different subsets of modules. Based on this estimated cost, the algorithm determines the subsequent nodes for all the modules. To validate its benefits, we simulate the proposed algorithm on a large number of random graphs, where it performs better than the most relevant benchmark, an adapted nearest neighbor algorithm for two separate agents, more than 84 percent of the time. For the second modular agent application, we consider the problem of optimal planning of modular buses to minimize the average passenger travel time. The individual modules can attach to form a joined vehicle and detach from other modules at any stop. Considering that the number of passenger boarding/deboarding the vehicles and the travel time between the stops are stochastic, we model the system using a Markov Decision Process (MDP). Due to the flexibility obtained with the modularity of the vehicles, the problem of minimizing passenger travel time boils down to optimally planning the actions, namely, stopping at the stop, skipping the stop, and attaching/detaching with other modules. Cost formulation is proposed to capture the effect of an action on the travel time of the affected passengers. The proposed policy selects the action corresponding to the given state's minimum cost. A previously proposed split policy for a modular bus system is used as a benchmark to compare with the proposed policy. The scheme is simulated using a high-fidelity bus system simulator and extensively compared with the cases when there is no control on the bus system, i.e., the vehicles serve every stop without split/join and the benchmark policy, and shown to perform better than both of these cases.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Aerospace Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Jagdale, Karan Suresh

Contributors dc:contributor

• Ornik, Melkior

• Planning
• Optimization
• Modular Agents

Statement dc:rights

• Copyright 2023 Karan Jagdale

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121358

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121358