Jaein Lim
(Advisor: Prof. Tsiotras)

will propose a doctoral thesis entitled,

DISTRIBUTED MULTI-AGENT PATH PLANNING

On

Friday, March 12 at 4:00 p.m.
https://bluejeans.com/605464113
 

Abstract
In real world planning problems, obtaining accurate models of the complex world is difficult, and the model itself becomes quickly out of date when the world is dynamic or uncertain. Plans made on uncertain models also become quickly obsolete and need to be updated accordingly. Unfortunately, changing a plan is not free. The need for a change of a plan implies that the resources used for planning or executing the previous plan may have been wasted. The question is then, how can an autonomous agent attain a more informative plan when its sensing and/or memory capabilities are limited and do not allow to build and plan on an accurate model of the environment? Fortunately, in many situations, the agent operates with other agents that can help to solve this problem. In this proposal, we study cooperative communication and planning strategies for a distributed multi-agent system to increase the search-space visibility, so that the agents can plan better as a team than alone. Our aim is to study cooperative communication and planning strategies for a team of agents with distributed local information to find a globally agreeable path in a graph representation of the planning environment.

Our approach is two-fold: first, we restrict the inter-agent communication to only relevant

information for finding a globally optimal solution, and second, we make each agent replan efficiently to find a new locally optimal solution when new information becomes available. Hence, by making each agent communicate less and replan more quickly, we make the communicated paths among the agents converge quickly to the globally optimal path. The fundamental questions are then: “what is relevant information in a partially known search space?” and “how should one reuse existing plans to facilitate a new plan?”. We address these questions in the modern paradigm of planning: heuristic-search, incremental-search, and lazy-search; and layout the proper machinery to build an efficient decision-making paradigm for multi-agent systems.

Committee

• Prof. Panagiotis Tsiotras – School of Aerospace Engineering (advisor)
• Prof. Seth Hutchinson– School of School of Interactive Computing
• Prof. Magnus Egerstedt– School of Electrical and Computer Engineering
• Prof. Siddhartha Srinivasa– School of Computer Science & Engineering, University of Washington