Recherche

Résultats de recherche

  • A Market-based Solution to the Multiple Traveling Salesmen Problem

    Article thumbnail: A Market-based Solution to the Multiple Traveling Salesmen Problem
    Type:
    Article
    Description/Abstract:
    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.
    Creator/Author:
    Cohen, Kelly; Kumar, Manish, and Kivelevitch, Elad
    Submitter:
    Kelly Cohen
    Date Uploaded:
    02/13/2017
    Date Modified:
    04/05/2017
    Date Created:
    2013-01
    License:
    All rights reserved

  • Market-Based Solution to the Allocation of Tasks to Agents

    Article thumbnail: Market-Based Solution to the Allocation of Tasks to Agents
    Type:
    Article
    Description/Abstract:
    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.
    Creator/Author:
    Cohen, Kelly; Kumar, Manish, and Kivelevitch, Elad
    Submitter:
    Kelly Cohen
    Date Uploaded:
    02/13/2017
    Date Modified:
    04/05/2017
    Date Created:
    2011-10
    License:
    All rights reserved

  • Genetic Fuzzy Trees and their Application Towards Autonomous Training and Control of a Squadron of Unmanned Combat Aerial Vehicles

    Article thumbnail: Genetic Fuzzy Trees and their Application Towards Autonomous Training and Control of a Squadron of Unmanned Combat Aerial Vehicles
    Type:
    Article
    Description/Abstract:
    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.
    Creator/Author:
    Schumacher, Corey; Cohen, Kelly; Ernest, Nicholas; Casbeer, David, and Kivelevitch, Elad
    Submitter:
    Kelly Cohen
    Date Uploaded:
    02/03/2017
    Date Modified:
    04/05/2017
    Date Created:
    2015-05
    License:
    All rights reserved

  • A Hierarchical Market Solution to the Min–Max Multiple Depots Vehicle Routing Problem

    Article thumbnail: A Hierarchical Market Solution to the Min–Max Multiple Depots Vehicle Routing Problem
    Type:
    Article
    Description/Abstract:
    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.
    Creator/Author:
    Sharma, Balaji R.; Cohen, Kelly; Ernest, Nicholas; Kumar, Manish, and Kivelevitch, Elad
    Submitter:
    Kelly Cohen
    Date Uploaded:
    02/03/2017
    Date Modified:
    04/05/2017
    Date Created:
    2014-01
    License:
    All rights reserved