ロボットネットワークにおける分散意思決定の性能限界
On the fundamental limitations of performance for distributed decision-making in robotic networks
ロボットネットワーク上の分散意思決定について、I/Oオートマタに基づく形式モデルを提案し、時間・メッセージ・バイト複雑性の限界を示した理論研究。
著者: Federico Rossi, Marco Pavone
分類: cs.MA, cs.RO
原文アブストラクト
This paper studies fundamental limitations of performance for distributed decision-making in robotic networks. The class of decision-making problems we consider encompasses a number of prototypical problems such as average-based consensus as well as distributed optimization, leader election, majority voting, MAX, MIN, and logical formulas. We first propose a formal model for distributed computation on robotic networks that is based on the concept of I/O automata and is inspired by the Computer Science literature on distributed computing clusters. Then, we present a number of bounds on time, message, and byte complexity, which we use to discuss the relative performance of a number of approaches for distributed decision-making. From a methodological standpoint, our work sheds light on the relation between the tools developed by the Computer Science and Controls communities on the topic of distributed algorithms.
