A Policy-Based Routing Scheme for Multi-Robot Systems

In this paper, we consider a policy-based routing scheme for a wireless communication network consisting of a set of robots as nodes. Our scheme provides a communication infrastructure that enables the multi-robot system to accomplish its assigned tasks. Our scheme is adaptive and can be implemented in a distributed manner by the nodes of the network. The scheme makes estimates of link and path costs in the network and uses these estimates to construct probabilistic routing tables in the nodes. We use ideas from the literature on simulation methods for approximate dynamic programming to compute, in a distributed manner, the cost estimates.We propose two schemes that update the probabilistic routing tables at the nodes of the network. One of the schemes is an adaptation of the Linear Reward Inaction rule found in studies of stochastic learning automata. Our other scheme is a modification of an Ant-Based Routing algorithm. We assume a simple model of the link behavior in the wireless network - a message transmission on a wireless link is assumed to be successful with a certain probability and is lost otherwise. We also analyze our algorithms and show that our probabilistic update schemes direct packets along paths with low costs.