Optimal Deterministic Protocols for Mobile Robots on a Grid |
| |
Authors: | Roberto Grossi Andrea Pietracaprina Geppino Pucci |
| |
Affiliation: | Dipartimento di Informatica, Università di Pisa, Corso Italia 40, Pisa, I-56125, Italyf1;Dipartimento di Elettronica e Informatica, Università di Padova, Via Gradenigo 6/a, Padua, I-35131, Italy, f2 |
| |
Abstract: | This paper studies a system of m robots operating in a set of n work locations connected by aisles in a
×
grid, where m≤n. From time to time the robots need to move along the aisles, in order to visit disjoint sets of locations. The movement of the robots must comply with the following constraints: (1) no two robots can collide at a grid node or traverse a grid edge at the same time; (2) a robot's sensory capability is limited to detecting the presence of another robot at a neighboring node. We present a deterministic protocol that, for any small constant ε>0, allows m≤(1-ε)n robots to visit their target locations in O(
) time, where each robot visits no more than d≤n targets and no target is visited by more than one robot. We also prove a lower bound showing that our protocol is optimal. Prior to this paper, no optimal protocols were known for d>1. For d=1, optimal protocols were known only for m≤
, while for general m≤n only a suboptimal randomized protocol was known. |
| |
Keywords: | Abbreviations: multirobot grid systemAbbreviations: routing protocolAbbreviations: meshAbbreviations: social lawsAbbreviations: computational agents |
本文献已被 ScienceDirect 等数据库收录! |
|