This letter develops two distributed algorithms to solve multi-robot task assignment problems (MTAP). We first describe MTAP as an integer linear programming (ILP) problem and then reformulate it as a relaxed convex o...
详细信息
This letter develops two distributed algorithms to solve multi-robot task assignment problems (MTAP). We first describe MTAP as an integer linear programming (ILP) problem and then reformulate it as a relaxed convex optimization problem. Based on the saddle-point dynamics, we propose two distributed optimization algorithms using optimistic gradient decent ascent (OGDA) and extra-gradient (EG) methods, which achieve exact convergence to an optimal solution of the relaxed problem. In most cases, such an solution reflects the optimality of the original ILP problems. For some special ILP problems, we provide a perturbation-based distributed method to avoid the inconsistency phenomenon, such that an optimal solution to any ILP problem is obtained. Compared with some decentralized algorithms requiring a central robot that communicates with the other robots, our developed algorithms are fully distributed, in which each robot only communicates with the nearest neighbors for an arbitrary connected graph. We evaluate the developed algorithms in terms of computation, communication, and data storage complexities, and compare them with some typical algorithms. It is shown that the developed algorithms have low computational and communication complexities. We also verify the effectiveness of our algorithms via numerical examples.
Due to the widespread application of multi-robot systems, the efficient taskassignment for a team of robots has become particularly critical for performing complex tasks. This paper studies the taskassignment proble...
详细信息
ISBN:
(纸本)9798350366907;9789887581581
Due to the widespread application of multi-robot systems, the efficient taskassignment for a team of robots has become particularly critical for performing complex tasks. This paper studies the taskassignment problem for multiple robots to visit a group of target locations with precedence constraints, which determine the order/sequence in which certain target locations need to be visited before others. A marginal-cost-based heuristic algorithm is developed to minimize the time for the robots to visit the last target location. The algorithm first uses a timestamp strategy to update the anticipated visiting time of each assigned target and the corresponding earliest time that each successor target can be visited under the precedence constraints. Then, it utilizes the topological sorting technique and the marginal-cost-based mechanism to insert the feasible target that induces the minimum marginal cost into the robots' current routes. Numerical simulations demonstrate the effectiveness of the proposed algorithm compared with the popular greedy algorithm and the existing simple iterative auction algorithm.
Due to the widespread application of multi-robot systems, the efficient taskassignment for a team of robots has become particularly critical for performing complex tasks. This paper studies the taskassignment proble...
详细信息
ISBN:
(数字)9789887581581
ISBN:
(纸本)9798350366907
Due to the widespread application of multi-robot systems, the efficient taskassignment for a team of robots has become particularly critical for performing complex tasks. This paper studies the taskassignment problem for multiple robots to visit a group of target locations with precedence constraints, which determine the order/sequence in which certain target locations need to be visited before others. A marginal-cost-based heuristic algorithm is developed to minimize the time for the robots to visit the last target location. The algorithm first uses a timestamp strategy to update the anticipated visiting time of each assigned target and the corresponding earliest time that each successor target can be visited under the precedence constraints. Then, it utilizes the topological sorting technique and the marginal-cost-based mechanism to insert the feasible target that induces the minimum marginal cost into the robots' current routes. Numerical simulations demonstrate the effectiveness of the proposed algorithm compared with the popular greedy algorithm and the existing simple iterative auction algorithm.
In this paper,A solution is proposed for the multi-robot task assignment in obstacle environment,which combines the A* algorithm with the genetic *** main work are twofold:(a) Path planning method based on A algorithm...
详细信息
ISBN:
(纸本)9781538629185
In this paper,A solution is proposed for the multi-robot task assignment in obstacle environment,which combines the A* algorithm with the genetic *** main work are twofold:(a) Path planning method based on A algorithm to search an optimal path between any robot and any target or any two targets;and(b) taskassignment method based on the genetic algorithm for the assignment of robots to targets so that the total distance traveled by all robots can be as minimum as *** experiments show that all the robots that have targets can avoid obstacle while performing the task with low cost and high velocity of convergence,meeting the real time requirements of multi-robot task assignment in obstacle environment.
In many missions, multiple robots need to cooperate to complete tasks. The workflow of these multi-robottasks involves forming coalitions of robots, assigning them to available tasks, and jointly executing the tasks....
详细信息
In many missions, multiple robots need to cooperate to complete tasks. The workflow of these multi-robottasks involves forming coalitions of robots, assigning them to available tasks, and jointly executing the tasks. In this article, we investigate such a workflow in an application-independent yet realistic setting. We abstract the key properties of tasks and robots and propose three distributed coalition formation and taskassignment methods. Distributed methods rely on a timely and accurate exchange of state information in multi-robot systems (MRS). Thus we focus on two important communication aspects: (i) how to achieve consistent coalition formation and taskassignment in the presence of communication faults, and (ii) how to reduce the communication effort required for the state updates in the MRS. In particular, we investigate the effect of event-triggered, time-triggered, and hybrid communication. We evaluate our distributed approaches in a simulation study using ns-3 and compare them with centralized methods and different network conditions. We demonstrate the sensitivity of complex missions to failure-prone MRS communication and provide robust, effective, and communication-aware methods for coalition formation and taskassignment.
Simultaneous Localization and Mapping(SLAM) stands as a vital technology for automatic control of *** significance of vision-based multi-robot collaborative SLAM technology is noteworthy in this domain,because visual ...
详细信息
Simultaneous Localization and Mapping(SLAM) stands as a vital technology for automatic control of *** significance of vision-based multi-robot collaborative SLAM technology is noteworthy in this domain,because visual SLAM uses cameras as the main sensor,which offers the benefits of easy access to environmental information and convenient *** the multi-robot system has the advantages of high efficiency,high fault tolerance,and high precision,so the multi-robot system can work in a complex environment and ensure its mapping efficiency,these may be a challenge for a single *** paper introduces the principles and common methods of visual SLAM,as well as the main algorithms of multi-robot collaborative *** paper analyzed the main problems existing in the current multi-robot collaborative visual SLAM technology:multi-robot SLAM task allocation,map fusion and back-end *** this paper listed different solutions,and analyzed their advantages and *** addition,this paper also introduces some future research prospects of multirobot collaborative visual SLAM technology,aiming to provide a reference direction for subsequent research in related fields.
This paper investigates the taskassignment problem for multiple dispersed robots constrained by limited communication *** robots are initially randomly distributed and need to visit several target locations while try...
详细信息
ISBN:
(纸本)9781538629185
This paper investigates the taskassignment problem for multiple dispersed robots constrained by limited communication *** robots are initially randomly distributed and need to visit several target locations while trying to minimize the total travel distance.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 taskassignment for the other ***,we propose a decentralized algorithm based on a single-traveling-salesman tour,which does not require all the robots to be connected through *** investigate the variation of the quality of the assignment solutions as the communication range *** proposed algorithms are compared with a centralized algorithm with shared global information and a decentralized greedy algorithm *** Carlo simulation results show the satisfying performance of the proposed algorithms.
暂无评论