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 consider the problem of minimising an inhomogeneous anisotropic elliptic functional in a class of closed $m$~dimensional subsets of~$\mathbf{R}^n$ which is stable under taking smooth deformations homotopic to identity and under local Hausdorff limits. We~prove that the minimiser exists inside the class and is an $(\mathscr H^m,m)$ rectifiable set in the sense of Federer. The class of competitors encodes a notion of spanning a~boundary. Read More

Strategic decisions to develop a mineral deposit are subject to geological uncertainty, due to the sparsity of drill core samples. The selection of metallurgical equipment is especially critical, since it restricts the processing options that are available to different ore blocks, even as the nature of the deposit is still highly uncertain. Current approaches for long-term mine planning are successful at addressing geological uncertainty, but do not adequately represent alternate modes of operation for the mineral processing plant, nor do they provide sufficient guidance for developing processing options. Read More

The nonnegative and positive semidefinite (PSD-) ranks are closely connected to the nonnegative and positive semidefinite extension complexities of a polytope, which are the minimal dimensions of linear and SDP programs which represent this polytope. Though some exponential lower bounds on the nonnegative and PSD- ranks has recently been proved for the slack matrices of some particular polytopes, there are still no tight bounds for these quantities. We explore some existing bounds on the PSD-rank and prove that they cannot give exponential lower bounds on the extension complexity. Read More

We study two generalizations of fractional variational problems by considering higher-order derivatives and a state time delay. We prove a higher-order integration by parts formula involving a Caputo fractional derivative of variable order and we establish several necessary optimality conditions for functionals containing a combined Caputo derivative of variable fractional order. Because the endpoint is considered to be free, we also deduce associated transversality conditions. Read More

In order to better understand micromechanical phenomena such as viscoelasticity and plasticity, the thermomechanical viewpoint is of prime importance but requires calorimetric measurements to be performed during a deformation process. Infrared imaging is commonly used to this aim but does not provide direct access to the intrinsic volumetric Thermomechanical Heat Sources (THS). An inversemethod is needed to convert temperature fields in the former quantity. Read More

We study the boundary structure of closed convex cones, with a focus on facially dual complete (nice) cones. These cones form a proper subset of facially exposed convex cones, and they behave well in the context of duality theory for convex optimization. Using the well-known and very commonly used concept of tangent cones in nonlinear optimization, we introduce some new notions for exposure of faces of convex sets. Read More

In this paper, we study the problem of finding the Euclidean distance to a convex cone generated by a set of discrete points in $\mathbb{R}^n_+$. In particular, we are interested in problems where the discrete points are the set of feasible solutions of some binary linear programming constraints. This problem has applications in manufacturing, machine learning, clustering, pattern recognition, and statistics. Read More

Using polynomial interpolation, along with structural properties of the family of positive real rational functions, we here show that a set of m nodes in the open left half of the complex plane, can always be mapped to anywhere in the complex plane by rational positive real functions whose degree is at most m. Moreover, we introduce an easy-to-find parametrization in $R^{2m+3}$ of a large subset of these interpolating functions. Read More

Appropriate selection of the penalty parameter is crucial to obtaining good performance from the Alternating Direction Method of Multipliers (ADMM). While analytic results for optimal selection of this parameter are very limited, there is a heuristic method that appears to be relatively successful in a number of different problems. The contribution of this paper is to demonstrate that their is a potentially serious flaw in this heuristic approach, and to propose a modification that at least partially addresses it. Read More

Multi stage stochastic programs arise in many applications from engineering whenever a set of inventories or stocks has to be valued. Such is the case in seasonal storage valuation of a set of cascaded reservoir chains in hydro management. A popular method is Stochastic Dual Dynamic Programming (SDDP), especially when the dimensionality of the problem is large and Dynamic programming no longer an option. Read More