Managing Communication Costs under Temporal Uncertainty
Managing Communication Costs under Temporal Uncertainty
Nikhil Bhargava, Christian Muise, Tiago Vaquero, Brian Williams
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 84-90.
https://doi.org/10.24963/ijcai.2018/12
In multi-agent temporal planning, individual agents cannot know a priori when other agents will execute their actions and so treat those actions as uncertain. Only when others communicate the results of their actions is that uncertainty resolved. If a full communication protocol is specified ahead of time, then delay controllability can be used to assess the feasibility of the temporal plan. However, agents often have flexibility in choosing when to communicate the results of their action. In this paper, we address the question of how to choose communication protocols that guarantee the feasibility of the original temporal plan subject to some cost associated with that communication. To do so, we introduce a means of extracting delay controllability conflicts and show how we can use these conflicts to more efficiently guide our search. We then present three conflict-directed search algorithms and explore the theoretical and empirical trade-offs between the different approaches.
Keywords:
Agent-based and Multi-agent Systems: Multi-agent Planning
Planning and Scheduling: Search in Planning and Scheduling
Planning and Scheduling: Planning and Scheduling