Target assignment for robots constrained by limited communication range

This paper investigates the task assignment problem for multiple dispersed robots constrained by limited communication range. The robots are initially randomly distributed and need to visit several target locations while minimizing the total travel time. A centralized rendezvous-based algorithm is proposed, under which all the robots first move towards a rendezvous position until communication paths are established between every pair of robots either directly or through intermediate peers, and then one robot is chosen as the leader to make a centralized task assignment for the other robots. Furthermore, we propose a decentralized algorithm based on a single-traveling-salesman tour, which does not require all the robots to be connected through communication. We investigate the variation of the quality of the assignment solutions as the level of information sharing increases and as the communication range grows, respectively. The proposed algorithms are compared with a centralized algorithm with shared global information and a decentralized greedy algorithm respectively. Monte Carlo simulation results show the satisfying performance of the proposed algorithms.

Similar Publications

We study controllability of a Partial Differential Equation of transport type, that arises in crowd models. We are interested in controlling such system with a control being a Lipschitz vector field on a fixed control set $\omega$. We prove that, for each initial and final configuration, one can steer one to another with such class of controls only if the uncontrolled dynamics allows to cross the control set $\omega$. Read More

A preconditioning strategy for the Powell-Hestenes-Rockafellar Augmented Lagrangian method (ALM) is presented. The scheme exploits the structure of the Augmented Lagrangian Hessian. It is a modular preconditioner consisting of two blocks. Read More

We prove a strong duality result for a linear programming problem which has the interpretation of being a discretised optimal Skorokhod embedding problem, and we recover this continuous time problem as a limit of the discrete problems. With the discrete setup we show that for a suitably chosen objective function, the optimiser takes the form of a hitting time for a random walk. In the limiting problem we then reprove the existence of the Root, Rost, and cave embedding solutions of the Skorokhod embedding problem. Read More

Integration of plug-in electric vehicles (PEVs) with distributed renewable resources will decrease PEVs' well-to-wheels greenhouse gas emissions, promote renewable power adoption and defer power system investments. This paper proposes a multidisciplinary approach to jointly planning PEV fast-charging stations and distributed photovoltaic (PV) power plants on coupled transportation and power networks. First, we develop models of 1) PEV fast-charging stations; 2) highway transportation networks under PEV driving range constraints; 3) PV power plants with reactive power control. Read More

This work proposes a research problem of finding sparse solution of undetermined Linear system with some applications. Two approaches how to solve the compressive sensing problem: using l_1 approach , the l_q approach with 0 < q < 1. Compressive sensing algorithms are designed to cope with ambiguities introduced by undersampling. Read More

A Learning Model Predictive Controller (LMPC) for linear system in presented. The proposed controller is an extension of the LMPC [1] and it aims to decrease the computational burden. The control scheme is reference-free and is able to improve its performance by learning from previous iterations. Read More

We study the online constrained ranking problem motivated by an application to web-traffic shaping: an online stream of sessions arrive in which, within each session, we are asked to rank items. The challenge involves optimizing the ranking in each session so that local vs. global objectives are controlled: within each session one wishes to maximize a reward (local) while satisfying certain constraints over the entire set of sessions (global). Read More

The paper defines a family of nested non-cooperative simultaneous finite games to study coalition structure formation with intra and inter-coalition externalities. Every game has two outcomes - an allocation of players over coalitions and a payoff profile for every player. Every game in the family has an equilibrium in mixed strategies. Read More

We consider the problem of bandit optimization, inspired by stochastic optimization and online learning problems with bandit feedback. In this problem, the objective is to minimize a global loss function of all the actions, not necessarily a cumulative loss. This framework allows us to study a very general class of problems, with applications in statistics, machine learning, and other fields. Read More

We consider 2-player zero-sum stochastic games where each player controls his own state variable living in a compact metric space. The terminology comes from gambling problems where the state of a player represents its wealth in a casino. Under natural assumptions (such as continuous running payoff and non expansive transitions), we consider for each discount factor the value v $\lambda$ of the $\lambda$-discounted stochastic game and investigate its limit when $\lambda$ goes to 0. Read More