Planning in modular multi-agent systems

Jagdale, Karan Suresh

Permalink

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

Description

Title

Planning in modular multi-agent systems

Author(s)

Jagdale, Karan Suresh

Issue Date

2023-07-17

Director of Research (if dissertation) or Advisor (if thesis)

Ornik, Melkior

Department of Study

Aerospace Engineering

Discipline

Aerospace Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

planning, optimization, modular agents

Abstract

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.

Graduation Semester

2023-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Karan Jagdale

Owning Collections