From Abstractions to Grounded Languages for Robust Coordination of Task Planning Robots

Individual robots in distributed systems must often coordinate to optimize the global performance. Where explicit coordination via communication is concerned, it is almost always achieved via a predefined "language" designed by human users. Such hand-designed languages tend to be either too rigid or too forgiving, leading to brittle solutions, excess negotiation costs, or unexpected coordination issues (e.g., deadlocks). In this paper, we consider a first step to bridge the gap for task planning robots using symbolic planning. Specifically, we study the automatic construction of languages that are maximally flexible while being sufficiently explicative for coordination. To this end, we view language as a machinery for specifying temporal-state constraints of plans. Such a view enables us to reverse-engineer a language from the ground up by mapping these composable constraints to words. Our language expresses a plan for any given task as a "plan sketch" to convey just-enough details while maximizing the flexibility to realize it, leading to robust coordination with optimality guarantees among other benefits. We formulate the problem, analyze it, and provide an approximate solution. We validate the advantages of our approach under various scenarios to shed light on its applications.