Recherche

Résultats de recherche

  • 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