Minimizing conflicts between moving agents over a set of non-homotopic paths through regret minimization

Andrew Kimmel, Kostas Bekris

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper considers a game-theoretic framework for motion coordination challenges. The focus of this work is to minimize the number of interactions agents have when moving through an environment. In particular, agents employ a replanning framework and regret minimization over a set of actions, which correspond to different homotopic paths. By associating a cost to each trajectory, a motion coordination game arises. Regret minimization is argued as an appropriate technique, as agents do not have any knowledge of other agents' cost functions. This work outlines a methodology for minimizing the regret of actions in a computationally efficient way. Initial simulation results involving pairs of mobile agents show indications that the proposed framework can improve the choice of non-colliding paths compared to a greedy choice by the agents, without increasing any information requirements.

Original languageEnglish (US)
Title of host publicationIntelligent Robotic Systems - Papers from the 2013 AAAI Workshop, Technical Report
PublisherAI Access Foundation
Number of pages7
ISBN (Print)9781577356219
StatePublished - 2013
Event2013 AAAI Workshop - Bellevue, WA, United States
Duration: Jul 14 2013Jul 15 2013

Publication series

NameAAAI Workshop - Technical Report


Other2013 AAAI Workshop
Country/TerritoryUnited States
CityBellevue, WA

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Minimizing conflicts between moving agents over a set of non-homotopic paths through regret minimization'. Together they form a unique fingerprint.

Cite this