Academic
Publications
A distributed auction algorithm for the assignment problem

A distributed auction algorithm for the assignment problem,10.1109/CDC.2008.4739098,Michael M. Zavlanos,Leonid Spesivtsev,George J. Pappas

A distributed auction algorithm for the assignment problem   (Citations: 8)
BibTex | RIS | RefWorks Download
The assignment problem constitutes one of the fundamental problems in the context of linear programming. Besides its theoretical significance, its frequent appearance in the areas of distributed control and facility allocation, where the problems' size and the cost for global computation and information can be highly prohibitive, gives rise to the need for local solutions that dynamically assign distinct agents to distinct tasks, while maximizing the total assignment benefit. In this paper, we consider the linear assignment problem in the context of networked systems, where the main challenge is dealing with the lack of global information due to the limited communication capabilities of the agents. We address this challenge by means of a distributed auction algorithm, where the agents are able to bid for the task to which they wish to be assigned. The desired assignment relies on an appropriate selection of bids that determine the prices of the tasks and render them more or less attractive for the agents to bid for. Up to date pricing information, necessary for accurate bidding, can be obtained in a multi-hop fashion by means of local communication between adjacent agents. Our algorithm is an extension to the parallel auction algorithm proposed by Bertsekas et al to the case where only local information is available and it is shown to always converge to an assignment that maximizes the total assignment benefit within a linear approximation of the optimal one.
Conference: Conference on Decision and Control - CDC , pp. 1212-1217, 2008
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Recently, [8], [9] have combined the auction algorithm with consensus algorithms in order to...
    • ...Recently, consensus algorithms have been combined with the auction algorithm, so that the shared memory/centralized auctioneer can be removed for solving the linear assignment problem [8], [9]...

    Lingzhi Luoet al. Multi-robot assignment algorithm for tasks with set precedence constra...

    • ...A multi-agent system in which agents have limited communication capabilities achieves an optimal target assignment solution if the global information is up- to-date and at the disposal of all decision makers (agents) at least in a multi-hop fashion; sufficient condition for optimal solution is that the communication graph among agents is connected [20,16]...
    • ...These as well as many other parallel and distributed algorithms for solving the assignment problem, e.g., [3,5,8,17,20], all assume the complete inter-agent communication graph, the latter with possibly substantial but bounded delays was a subject of [3,8,20]...
    • ...These as well as many other parallel and distributed algorithms for solving the assignment problem, e.g., [3,5,8,17,20], all assume the complete inter-agent communication graph, the latter with possibly substantial but bounded delays was a subject of [3,8,20]...

    Marin Lujaket al. On the Communication Range in Auction-Based Multi-Agent Target Assignm...

    • ...To solve the target-assignment problem in a distributed way, we adapt the algorithm in [15], and for the exploration of the environment we use the Q-Learning algorithm introduced in [12]...
    • ...More recently, a distributed version was proposed in [15], with the requirement that the network of agents be jointly connected sufficiently often over time...
    • ...In [6], the distributed sequential augmenting path algorithm is employed to solve assignment problems...
    • ...As opposed to the algorithm given in [15], the JOLEAS algorithm do not require agents to have a priori information about the assignment benefits associated with given targets; moreover, these benefits may change with time...
    • ...Our exposition on the auction algorithm follows [4] and [15]...
    • ...More precisely, in the distributed auction algorithm [15], suppose agent i believes that matching with object j has the price pij(t)...
    • ...Remark 1: The main difference between the auction algorithm part in the description above (Steps 24-29) and the distributed auction algorithm presented in [15] is the following...
    • ...All in all, our algorithm extends the distributed auction algorithm presented in [15] in that we make it robust to agent failure, and capable of dealing with unknown environments...
    • ...The algorithm was designed as an integration of the Q-Learning algorithm and the distributed auction algorithm presented in [15]...

    Teymur Sadikhovet al. A distributed joint-learning and auction algorithm for target assignme...

    • ...This is not valid in distributed memory situations where processors share information with each other following a particular network topology [7]...
    • ...Other attempts to implement the auction on a parallel system include [8], [9], [7], [10], [11]...

    Amgad Naiemet al. A centrally coordinated parallel auction algorithm for large scale ass...

Sort by: