Name
Abstract | ||
|---|---|---|
uction and market-based mechanisms are among the most popular methods for distributed task allocation in multi-robot systems. Most of these mechanisms were designed in a heuristic way and analysis of the quality of the resulting assignment solution is rare. This paper presents a new market-based multi-robot task allocation algorithm that produces optimal assignments. Rather than adopting a buyer's "selfish" bidding perspective as in previous auction/market-based approaches, the proposed method approaches auctioning from a merchant's point of view, producing a pricing policy that responds to cliques of customers and their preferences. The algorithm uses price escalation to clear a market of all its items, producing a state of equilibrium that satisfies both the merchant and customers. This effectively assigns all robots to their tasks. The proposed method can be used as a general assignment algorithm as it has a time complexity ( $$O(n^3 \text {lg} n)$$ O ( n 3 lg n ) ) close to the fastest state-of-the-art algorithms ( $$O(n^3)$$ O ( n 3 ) ) but is extremely easy to implement. As in previous research, the economic model reflects the distributed nature of markets inherently: in this paper it leads directly to a decentralized method ideally suited for distributed multi-robot systems. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s10514-014-9403-2 | Autonomous Robots |
Keywords | DocType | Volume |
Task Allocation,Combinatorial Auction,Auction Algorithm,Price Increment,Utility Matrix | Journal | 37 |
Issue | ISSN | Citations |
4 | 0929-5593 | 1 |
PageRank | References | Authors |
0.35 | 24 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lantao Liu | 1 | 157 | 16.49 |
| Dylan A. Shell | 2 | 334 | 47.94 |
| Nathan Michael | 3 | 1892 | 131.29 |