Résultats de recherche pour « Task Allocation »

This paper addresses task allocation to coordinate a fleet of autonomous vehicles by presenting two decentralized algorithms: the consensus-based auction algorithm (CBAA) and its generalization to the multi-assignment problem, i.e., the consensus-based bundle algorithm (CBBA). These algorithms utilize a market-based decision strategy as the mechanism for decentralized task selection and use a consensus routine based on local communication as the conflict resolution mechanism to achieve agreement on the winning bid values. Under reasonable assumptions on the scoring scheme, both of the proposed algorithms are proven to guarantee convergence to a conflict-free assignment, and it is shown that the converged solutions exhibit provable worst-case performance. It is also demonstrated that CBAA and CBBA produce conflict-free feasible solutions that are robust to both inconsistencies in the situational awareness across the fleet and variations in the communication network topology. Numerical experiments confirm superior convergence properties and performance when compared with existing auction-based task-allocation algorithms.

This paper deals with the task allocation problem in multi-robot systems. We propose a completely distributed architecture, where robots dynamically allocate their tasks while they are building their plans. We first focus on the problem of simple "goto" tasks allocation: our approach involves an incremental task allocation algorithm based on the Contract-Net protocol. We introduce a parameter called equity coefficient in order to equilibrate the workload between the different robots and to control the triggering of the auction process. Then, we address the problem raised by temporal constraints between tasks by dynamically specifying temporary hierarchies among the tasks. Tests run in simulation quantify the benefits of our improvements.

This paper presents an efficient algorithm to solve one of the task allocation problems. Task assignment in an heterogeneous multiple processors system is investigated. The cost function is formulated in order to measure the intertask communication and processing costs in an uncapacited network. A formulation of the problem in terms of the minimization of a submodular quadratic pseudo-Boolean function with assignment constraints is then presented. The use of a branch-and-bound algorithm using a Lagrangean relaxation of these constraints is proposed. The lower bound is the value of an approximate solution to the Lagrangean dual problem. A zero-duality gap, that is, a saddle point, is characterized by checking the consistency of a pseudo-Boolean equation. A solution is found for large-scale problems (e.g., 20 processors, 50 tasks, and 200 task communications or 10 processors, 100 tasks, and 300 task communications). Excellent experimental results were obtained which are due to the weak frequency of a duality gap and the efficient characterization of the zero-gap (for practical purposes, this is achieved in linear time). Moreover, from the saddle point, it is possible to derive the optimal task assignment.

We present a scalable approach to dynamically allocating a swarm of homogeneous robots to multiple tasks, which are to be performed in parallel, following a desired distribution. We employ a decentralized strategy that requires no communication among robots. It is based on the development of a continuous abstraction of the swarm obtained by modeling population fractions and defining the task allocation problem as the selection of rates of robot ingress and egress to and from each task. These rates are used to determine probabilities that define stochastic control policies for individual robots, which, in turn, produce the desired collective behavior. We address the problem of computing rates to achieve fast redistribution of the swarm subject to constraint(s) on switching between tasks at equilibrium. We present several formulations of this optimization problem that vary in the precedence constraints between tasks and in their dependence on the initial robot distribution. We use each formulation to optimize the rates for a scenario with four tasks and compare the resulting control policies using a simulation in which 250 robots redistribute themselves among four buildings to survey the perimeters.

Multi-agent systems and especially unmanned vehicles, are a crucial part of the solution to a lot of real world problems, making essential the improvement of task allocation techniques. In this review, we present the main techniques used for task allocation algorithms, categorising them based on the techniques used, focusing mainly on recent works. We also analyse these methods, focusing mainly on their complexity, optimality and scalability. We also refer to common communication schemes used in task allocation methods, as well as to the role of uncertainty in task allocation. Finally, we compare them based on the above criteria, trying to find gaps in the literature and to propose the most promising ones.

Abstract Unmanned aerial vehicles, can offer solutions to a lot of problems, making it crucial to research more and improve the task allocation methods used. In this survey, the main approaches used for task allocation in applications involving UAVs are presented as well as the most common applications of UAVs that require the application of task allocation methods. They are followed by the categories of the task allocation algorithms used, with the main focus being on more recent works. Our analysis of these methods focuses primarily on their complexity, optimality, and scalability. Additionally, the communication schemes commonly utilized are presented, as well as the impact of uncertainty on task allocation of UAVs. Finally, these methods are compared based on the aforementioned criteria, suggesting the most promising approaches.

Faster and more cost-efficient, crowdsourced delivery is needed to meet the growing customer demands of many industries, including online shopping, on-demand local delivery, and on-demand transportation. The power of crowdsourced delivery stems from the large number of workers potentially available to provide services and reduce costs. It has been shown in social psychology literature that fairness is key to ensuring high worker participation. However, existing assignment solutions fall short on modeling the dynamic fairness metric. In this work, we introduce a new assignment strategy for crowdsourced delivery tasks. This strategy takes fairness towards workers into consideration, while maximizing the task allocation ratio. Since redundant assignments are not possible in delivery tasks, we first introduce a 2-phase allocation model that increases the reliability of a worker to complete a given task. To realize the effectiveness of our model in practice, we present both offline and online versions of our proposed algorithm called F-Aware. Given a task-to-worker bipartite graph, F-Aware assigns each task to a worker that minimizes unfairness, while allocating tasks to use worker capacities as much as possible. We present an evaluation of our algorithms with respect to running time, task allocation ratio (TAR), as well as unfairness and assignment ratio. Experiments show that F-Aware runs around 107× faster than the TAR-optimal solution and allocates 96.9 percent of the tasks that can be allocated by it. Moreover, it is shown that, F-Aware is able to provide a much fair distribution of tasks to workers than the best competitor algorithm.