Seminar on From Fast Kebab Delivery to Modularity: Complex Scenarios in Multi-Agent, Multi-Target Planning

Assistant Professor Melkior Ornik

University of Illinois Urbana-Champaign in Urbana, USA

Fast, successful, and efficient multi-target planning is a core challenge for complex missions with multiple autonomous agents. The obstacles are seemingly insurmountable: joint planning notoriously suffers from the curse of dimensionality, while even planning for a single agent results in NP-hard combinatorial optimization problems such as the traveling salesman problem. As a result, application domains traditionally rely on human-driven solutions or simple heuristics to produce possibly vastly suboptimal plans. The purpose of this talk is to show that there may exist a middle road. By following three problems in multi-target planning –time-optimal planning, minimum latency, and planning for modular agents – we will show that planning with implicit or explicit mechanism design can be successfully used to induce desirable long-term behavior without explicit long-term planning. In the relevant domains, such an approach can easily outperform existing benchmarks while retaining the capability to operate at an appropriately large scale.