Improving Computational Efficiency in Crowded Task Allocation Games with Coupled Constraints
Source abstract
Abstract
Multi-agent task allocation is a well-studied field with many proven algorithms. In real-world applications, many tasks have complicated coupled relationships that affect the feasibility of some algorithms. In this paper, we leverage on the properties of potential games and introduce a scheduling algorithm to provide feasible solutions in allocation scenarios with complicated spatial and temporal dependence. Additionally, we propose the use of random sampling in a Distributed Stochastic Algorithm to enhance speed of convergence. We demonstrate the feasibility of such an approach in a simulated disaster relief operation and show that feasibly good results can be obtained when the confirmation and sample size requirements are properly selected.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Auction Theory and Applications · Game Theory and Applications · Optimization and Search Problems
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Aerospace Engineering & KI for Robotics, Korea Advanced Institute of Science and Technology, Daejeon 34141, Korea
Funding
Institute for Information and communications Technology Promotion
References (34)
Show source-provided references
1. Autonomous vehicle-target assignment: A game-theoretical formulation10.1115/1.2766722 ↗
2. Chapman, A.C., Micillo, R.A., Kota, R., and Jennings, N.R. (2009, January 10–15). Decentralised dynamic task allocation: A practical game: Theoretic approach. Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems, Budapest, Hungary.
3. Consensus-based decentralized auctions for robust task allocation10.1109/TRO.2009.2022423 ↗
4. Sold!: Auction methods for multirobot coordination10.1109/TRA.2002.803462 ↗
5. Li, N., and Marden, J.R. (2010, January 15–17). Designing games to handle coupled constraints. Proceedings of the 49th IEEE Conference on Decision and Control (CDC), Atlanta, GA, USA.10.1109/CDC.2010.5718136 ↗
6. Decoupling coupled constraints through utility design10.1109/TAC.2014.2304373 ↗
7. Building multirobot coalitions through automated task solution synthesis10.1109/JPROC.2006.876933 ↗
8. Whitten, A.K., Choi, H.L., Johnson, L.B., and How, J.P. (July, January 29). Decentralized task allocation with coupled constraints in complex missions. Proceedings of the 2011 American Control Conference, San Francisco, CA, USA.10.1109/ACC.2011.5990917 ↗
9. Netto, R., Ramalho, G., Bonatto, B., Carpinteiro, O., Zambroni de Souza, A., Oliveira, D., and Braga, R. (2018). Real-Time Framework for Energy Management System of a Smart Microgrid Using Multiagent Systems. Energies, 11.10.20944/preprints201801.0113.v1 ↗
10. Han, Q., Tan, G., Fu, X., Mei, Y., and Yang, Z. (2018). Water resource optimal allocation based on multi-agent game theory of HanJiang river basin. Water, 10.10.3390/w10091184 ↗
11. Baldoni, M., Baroglio, C., May, K.M., Micalizio, R., and Tedeschi, S. (2018). Computational Accountability in MAS Organizations with ADOPT. Appl. Sci., 8.10.3390/app8040489 ↗
12. Joint strategy fictitious play with inertia for potential games10.1109/TAC.2008.2010885 ↗
13. Bowling, M., and Veloso, M. (2000). An Analysis of Stochastic Game Theory for Multiagent Reinforcement Learning, Carnegie-Mellon Univ Pittsburgh Pa School of Computer Science. Technical Report.
14. Heinrich, J., and Silver, D. (2016). Deep reinforcement learning from self-play in imperfect-information games. arXiv.
15. A Modified Q-Learning Algorithm for Potential Games10.3182/20140824-6-ZA-1003.02646 ↗
16. Lim, M.C., and Choi, H.L. (2017, January 13–15). A Game-Theoretic Approach for Multi-Robot Task Allocation with Dependency Constraints. Proceedings of the 5th International Conference of Robot Intelligence Technology and Applications, Daejeon, Korea.
17. Potential games10.1006/game.1996.0044 ↗
18. Chapman, A., Rogers, A., and Jennings, N.R. (2016, December 05). A Parameterisation of Algorithms for Distributed Constraint Optimisation via Potential Games. Available online: https://eprints.soton.ac.uk/265208/.
19. Lã, Q.D., Chew, Y.H., and Soong, B.H. (2016). Potential Game Theory: Applications in Radio Resource Allocation, Springer.10.1007/978-3-319-30869-2 ↗
20. Cooperative control and potential games10.1109/TSMCB.2009.2017273 ↗
21. A potential game approach for information-maximizing cooperative planning of sensor networks10.1109/TCST.2015.2403475 ↗
22. Macarthur, K.S., Stranders, R., Ramchurn, S.D., and Jennings, N.R. (2011, January 7–11). A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.10.1609/aaai.v25i1.7866 ↗
23. Lim, M.C. (2018). A Game-Theoretic Approach for Coupled-Constraint Task Allocation. [Master’s Thesis, Korea Advanced Institute of Science and Technology].
24. Benchmarking hybrid algorithms for distributed constraint optimisation games10.1007/s10458-010-9128-3 ↗
25. Garivier, A., Kaufmann, E., and Koolen, W.M. (2016, January 23–26). Maximin action identification: A new bandit framework for games. Proceedings of the Conference on Learning Theory, New York, NY, USA.
26. Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation10.1016/j.geb.2012.03.006 ↗
27. Borowski, H., Marden, J.R., and Frew, E.W. (2013, January 10–13). Fast convergence in semi-anonymous potential games. Proceedings of the IEEE 52nd Annual Conference on Decision and Control, Florence, Italy.10.1109/CDC.2013.6760242 ↗
28. Tumer, K., Agogino, A.K., and Wolpert, D.H. (2002, January 15–19). Learning sequences of actions in collectives of autonomous agents. Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems: Part 1, Bologna, Italy.10.1145/544829.544832 ↗
29. Tumer, K., and Wolpert, D. (2004). A survey of collectives. Collectives and the Design of Complex Systems, Springer.10.1007/978-1-4419-8909-3 ↗
30. Juhele (2019, February 23). City after Earthquake [PNG File]. Available online: https://openclipart.org/detail/250253/city-after-earthquake.
31. Markacio (2019, February 23). Construction Crane [PNG File]. Available online: https://openclipart.org/detail/168285/construction-crane.
32. Rdevries (2019, February 23). Fire Truck [PNG File]. Available online: https://openclipart.org/detail/190874/fire-truck.
33. Ginkgo (2019, February 23). Isometric Ambulance [PNG File]. Available online: https://openclipart.org/detail/252628/isometric-ambulance.
34. Oksmith (2019, February 23). Injured [PNG File]. Available online: https://openclipart.org/detail/285043/injured.