Buscar
Filtrado por:
Creador
Kivelevitch, Elad
Eliminar la restricciónCreador: Kivelevitch, Elad
1 - 4 de 4
El número de resultados a mostrar por página
Resultados de la búsqueda
- Type:
- Article
- Descripción/Resumen:
- This paper describes a market-based solution to the problem of assigning mobile agents to tasks. The problem is formulated as the multiple depots, multiple traveling salesmen problem (MTSP), where agents and tasks operate in a market to achieve near-optimal solutions. We consider both the classical MTSP, in which the sum of all tour lengths is minimized, and the Min-Max MTSP, in which the longest tour is minimized. We compare the market-based solution with direct enumeration in small scenarios, and show that the results are nearly optimal. For the classical MTSP, we compare our results to linear programming, and show that the results are within 1 % of the best cost found by linear programming in more than 90 % of the runs, with a significant reduction in runtime. For the Min-Max case, we compare our method with Carlsson's algorithm and show an improvement of 5 % to 40 % in cost, albeit at an increase in runtime. Finally, we demonstrate the ability of the market-based solution to deal with changes in the scenario, e.g., agents leaving and entering the market. We show that the market paradigm is ideal for dealing with these changes during runtime, without the need to restart the algorithm, and that the solution reacts to the new scenarios in a quick and near-optimal way.
- Creador/Autor:
- Cohen, Kelly; Kumar, Manish, and Kivelevitch, Elad
- Peticionario:
- Kelly Cohen
- Fecha modificada:
- 02/13/2017
- Fecha modificada:
- 04/05/2017
- Fecha de creacion:
- 2013-01
- Licencia:
- All rights reserved
- Type:
- Article
- Descripción/Resumen:
- Tasks allocation is a fundamental problem in multiagent systems. We formulate the problem as a multiple traveling salesmen problem (MTSP), which is an extension to the well known traveling salesman problem (TSP), both considered to be NP-hard combinatorial optimization problems. We propose a solution in which agents interact in an economic market to win tasks situated in an environment. The agents strive to minimize required costs, defined as either the total distance traveled by all agents or the maximum distance traveled by any agent. Using a set of simple market operations, the agents come up with a solution for task allocation. In this work we examine the processing speed of the market-based solution (MBS), as well as the quality vs. optimal solutions achieved using enumeration for a 3 agents by 8 tasks scenario. We show that the MBS is both quick and close to optimal. We then show that the MBS can be scaled to more complicated problems, by comparing its results with results from genetic algorithm (GA) and clustering. We also show the robustness of the MBS to changes in the scenario, e.g. the addition and removal of tasks or agents.
- Creador/Autor:
- Cohen, Kelly; Kumar, Manish, and Kivelevitch, Elad
- Peticionario:
- Kelly Cohen
- Fecha modificada:
- 02/13/2017
- Fecha modificada:
- 04/05/2017
- Fecha de creacion:
- 2011-10
- Licencia:
- All rights reserved
- Type:
- Article
- Descripción/Resumen:
- This study introduces the technique of Genetic Fuzzy Trees (GFTs) through novel application to an air combat control problem of an autonomous squadron of Unmanned Combat Aerial Vehicles (UCAVs) equipped with next-generation defensive systems. GFTs are a natural evolution to Genetic Fuzzy Systems, in which multiple cascading fuzzy systems are optimized by genetic methods. In this problem a team of UCAV's must traverse through a battle space and counter enemy threats, utilize imperfect systems, cope with uncertainty, and successfully destroy critical targets. Enemy threats take the form of Air Interceptors (AIs), Surface to Air Missile (SAM) sites, and Electronic WARfare (EWAR) stations. Simultaneous training and tuning a multitude of Fuzzy Inference Systems (FISs), with varying degrees of connectivity, is performed through the use of an optimized Genetic Algorithm (GA). The GFT presented in this study, the Learning Enhanced Tactical Handling Algorithm (LETHA), is able to create controllers with the presence of deep learning, resilience to uncertainties, and adaptability to changing scenarios. These resulting deterministic fuzzy controllers are easily understandable by operators, are of very high performance and efficiency, and are consistently capable of completing new and different missions not trained for.
- Creador/Autor:
- Schumacher, Corey; Cohen, Kelly; Ernest, Nicholas; Casbeer, David, and Kivelevitch, Elad
- Peticionario:
- Kelly Cohen
- Fecha modificada:
- 02/03/2017
- Fecha modificada:
- 04/05/2017
- Fecha de creacion:
- 2015-05
- Licencia:
- All rights reserved
- Type:
- Article
- Descripción/Resumen:
- The problem of assigning a group of Unmanned Aerial Vehicles (UAVs) to perform spatially distributed tasks often requires that the tasks will be performed as quickly as possible. This problem can be defined as the Min–Max Multiple Depots Vehicle Routing Problem (MMMDVRP), which is a benchmark combinatorial optimization problem. In this problem, UAVs are assigned to service tasks so that each task is serviced once and the goal is to minimize the longest tour performed by any UAV in its motion from its initial location (depot) to the tasks and back to the depot. This problem arises in many time-critical applications, e.g. mobile targets assigned to UAVs in a military context, wildfire fighting, and disaster relief efforts in civilian applications. In this work, we formulate the problem using Mixed Integer Linear Programming (MILP) and Binary Programming and show the scalability limitation of these formulations. To improve scalability, we propose a hierarchical market-based solution (MBS). Simulation results demonstrate the ability of the MBS to solve large scale problems and obtain better costs compared with other known heuristic solution.
- Creador/Autor:
- Sharma, Balaji R.; Cohen, Kelly; Ernest, Nicholas; Kumar, Manish, and Kivelevitch, Elad
- Peticionario:
- Kelly Cohen
- Fecha modificada:
- 02/03/2017
- Fecha modificada:
- 04/05/2017
- Fecha de creacion:
- 2014-01
- Licencia:
- All rights reserved