Approximate Dynamic Programming for Relay Deployment in Multi-robot System

We consider the scenario where a robot squadron navigates along pre-set routes, collects monitored data and sends the collected data to a remote base-station. When the robot squadron moves distant from the base station, a communication relay may be applied in order to provide satisfactory communication quality. Meanwhile, the energy consumption by the relay should be minimized in order to prolong the operation of the system. Hence, this paper aims at optimally deploying the communication relay so that the total energy consumption is minimized under the premise of ensuring the quality of communication. The initial idea is to employ dynamic programming (DP), but DP incurs a high computational complexity and may not be scalable. Therefore, we proposed two approximate optimization techniques, namely the relay-range limited DP (RRL-DP) and multi-phase optimization scheme (MPOS). It is shown that both RRL-DP and MPOS may greatly reduce the computation cost while maintaining the optimality of DP. Finally, we propose an amalgamated MPOS-RRL-DP method that exploits the benefits of both the RRL-DP and MPOS, and it is shown that MPOS-RRL-DP may strike a beneficial tradeoff between computational complexity and total energy optimization in order to meet various practical requirements. Specifically, for the considered scenario, MPOS-RRL-DP achieves a ~50× speed up at a cost of marginal ~0.04% energy loss in comparison to conventional DP.