Discovering Near-Optimal Communication Network for Modular Robots
Harris Chiu and Wei-Min Shen. Discovering Near-Optimal Communication Network for Modular Robots. In Proc. 2011 IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems, San Francisco, CA, October 2011. IROS 2011 Workshop on Reconfigurable Modular Robotics
Download
Abstract
Neighbor-to-Neighbor (Inter-Module) communication between modules using methods such as infrared, radio and bus-type connection are critical component for global behavior coordination. However, this type of communication method does not necessarily provide the shortest possible routes between modules and not making use of Hidden Communication Shortcuts (HCS). A HCS is de?ned as a communication channel between two modules without involving any inter-module (nonHCS) communication. For example, instead of sending messages through all modules in a snake confguration, the head module can directly talk to the tail module through infra-red if they are physically close. This paper proposes a novel way to discover existing communication shortcuts distributedly and form a near-optimal network using these shortcuts to connect a set of given terminal modules based on inter-module communication. The size of the discovered network is at most two times larger than the optimal (minimal) ones. To make this approach more realistic, we assume that not all communication devices on the modules are turned on simultaneously and in fact no more than r modules are allowed to turn on devices for non inter-module communication at the same time to avoid interferences. Derived from a centralized network deployment approach of mobile robot network - ANCHOR [7], this paper provides (1) a distributed algorithm for HCS discovery among modular robots (2) with adaptation to heterogeneity as long as the modular robots are connected at least with neighbor-toneighbor communication (3) a distributed approach to form a near-optimal network with at most two times the minimum number of modules (2-OPT) to activate their devices for HCS. We show that the convergence time on a balanced confguration is of a factor t, O(n2t), where n and t are the number of modules and terminal modules respectively, but it remains O(n2) for the total number of activation and deactivation of devices for HCS. In simulation, we also show the improvement of convergence time as r increases
BibTeX Entry
@InProceedings{chiu2011-discovering-communication-network,
abstract = {Neighbor-to-Neighbor (Inter-Module) communication between modules using methods such as infrared, radio and bus-type connection are critical component for global behavior coordination. However, this type of communication method does not necessarily provide the shortest possible routes between modules and not making use of Hidden Communication Shortcuts (HCS). A HCS is de?ned as a communication channel
between two modules without involving any inter-module (nonHCS) communication. For example, instead of sending messages through all modules in a snake confguration, the head module can directly talk to the tail module through infra-red if they are physically close. This paper proposes a novel way to discover existing communication shortcuts distributedly and form a
near-optimal network using these shortcuts to connect a set of given terminal modules based on inter-module communication. The size of the discovered network is at most two times larger than the optimal (minimal) ones. To make this approach more realistic, we assume that not all communication devices on the modules are turned on simultaneously and in fact no more than
r modules are allowed to turn on devices for non inter-module communication at the same time to avoid interferences. Derived from a centralized network deployment approach of mobile robot network - ANCHOR [7], this paper provides (1) a distributed algorithm for HCS discovery among modular robots (2) with adaptation to heterogeneity as long as the modular robots are connected at least with neighbor-toneighbor communication (3) a distributed approach to form
a near-optimal network with at most two times the minimum number of modules (2-OPT) to activate their devices for HCS. We show that the convergence time on a balanced confguration is of a factor t, O(n2t), where n and t are the number of modules and terminal modules respectively, but it remains O(n2) for the total number of activation and deactivation of devices for HCS.
In simulation, we also show the improvement of convergence time as r increases},
address = {San Francisco, CA},
author = {Harris Chiu and Wei-Min Shen},
booktitle = iros-11,
month = oct,
note = {IROS 2011 Workshop on Reconfigurable Modular Robotics},
title = {Discovering Near-Optimal Communication Network for Modular Robots},
year = {2011}
}
