Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(8)
Assignment Problem
Distributed Control
Global Computing
Linear Approximation
Local Community
Networked Systems
Linear Assignment Problem
Linear Program
Subscribe
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
Edit
A distributed auction algorithm for the assignment problem
(
Citations: 8
)
BibTex

RIS

RefWorks
Download
Michael M. Zavlanos
,
Leonid Spesivtsev
,
George J. Pappas
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 multihop 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. 12121217, 2008
DOI:
10.1109/CDC.2008.4739098
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.
(
www.cis.upenn.edu
)
(
dx.doi.org
)
(
www.seas.upenn.edu
)
(
www.informatik.unitrier.de
)
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
More »
Citation Context
(4)
...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 Luo
,
et al.
Multirobot assignment algorithm for tasks with set precedence constra...
...A multiagent system in which agents have limited communication capabilities achieves an optimal target assignment solution if the global information is up todate and at the disposal of all decision makers (agents) at least in a multihop 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 interagent 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 interagent communication graph, the latter with possibly substantial but bounded delays was a subject of [3,8,
20
]...
Marin Lujak
,
et al.
On the Communication Range in AuctionBased MultiAgent Target Assignm...
...To solve the targetassignment problem in a distributed way, we adapt the algorithm in [
15
], and for the exploration of the environment we use the QLearning 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 2429) 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 QLearning algorithm and the distributed auction algorithm presented in [
15
]...
Teymur Sadikhov
,
et al.
A distributed jointlearning 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 Naiem
,
et al.
A centrally coordinated parallel auction algorithm for large scale ass...
References
(30)
Combinatorial Optimization: Algorithms and Complexity
(
Citations: 2722
)
Christos H. Papadimitriou
,
Kenneth Steiglitz
Published in 1982.
The TravelingSalesman Problem and Minimum Spanning Trees
(
Citations: 416
)
M. Held
,
R. M. Karp
Journal:
Operations Research
, vol. 18, no. 6, pp. 11381162, 1970
Dynamic Assignment in Distributed Motion Planning With Local Coordination
(
Citations: 24
)
Michael M. Zavlanos
,
George J. Pappas
Journal:
IEEE Transactions on Robotics  TRob
, vol. 24, no. 1, pp. 232242, 2008
Target assignment for robotic networks: Worstcase and stochastic performance in dense environments
(
Citations: 5
)
Stephen L. Smith
,
Francesco Bullo
Conference:
Conference on Decision and Control  CDC
, pp. 35853590, 2007
Distributed formation control with permutation symmetries
(
Citations: 8
)
Michael M. Zavlanos
,
George J. Pappas
Conference:
Conference on Decision and Control  CDC
, pp. 28942899, 2007
Sort by:
Citations
(8)
Image and animation display with multiple mobile robots
Javier AlonsoMora
,
Andreas Breitenmoser
,
Martin Rufli
,
Roland Siegwart
,
Paul Beardsley
Journal:
International Journal of Robotic Research  IJRR
, vol. 31, no. 6, pp. 753773, 2012
Multirobot assignment algorithm for tasks with set precedence constraints
Lingzhi Luo
,
Nilanjan Chakraborty
,
Katia Sycara
Conference:
International Conference on Robotics and Automation  ICRA
, pp. 25262533, 2011
On the Communication Range in AuctionBased MultiAgent Target Assignment
Marin Lujak
,
Stefano Giordani
Conference:
International Workshop on SelfOrganizing Systems  IWSOS
, pp. 3243, 2011
A Distributed Algorithm for the MultiRobot Task Allocation Problem
(
Citations: 1
)
Stefano Giordani
,
Marin Lujak
,
Francesco Martinelli
Conference:
Industrial and Engineering Applications of Artificial Intelligence and Expert Systems  IEA/AIE
, pp. 721730, 2010
A distributed jointlearning and auction algorithm for target assignment
Teymur Sadikhov
,
Minghui Zhu
,
Sonia Martínez
Conference:
Conference on Decision and Control  CDC
, pp. 54505455, 2010