Abstract
Multi-robot task allocation is a well known and widely researched decision-making problem that is difficult to solve in reasonable time even for small instances. Additional complexity is added by the fact that the parameters of the system may change over time, which happens either by external stimuli or by the task execution itself. One of the common causes behind these changes is the movement of executors or tasks. This paper tackles a problem of multi-task, multi-robot allocation in a such an environment. Formulated and solved is a specific decision-making problem. Performed is an experimental comparison of a dedicated solution algorithm with known methods for the more general Multidimensional Knapsack and Covering problem. Empirical evaluation illustrates that a dedicated approach is competitive and often necessary, as the general approach proves to be too slow.
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
[AHL] Arntzen, H., Hvattum L., Lokketangen A.: Adaptive memory search for multi- demand multidimensional knapsack problems. Computers & Operations Research 33, pp. 2508–2525. Elsevier (2005)
[CV] Coltin B., Veloso M., Mobile Robot Task Allocation in Hybrid Wireless Sensor Networks, Proceedings of International Conference on Intelligent Robots and Systems, pp. 2932–2937 (2010)
[CM] Correll N., Martinoli A., Multirobot Inspection of Industrial Machinery, IEEE Robotics and Automation Magazine, Vol. 16, pp. 103–112 (2009)
[Ho1] Hojda M., Task allocation in robot systems with multi-modal capabilities, IFAC-PapersOnLine, 15th IFAC Symposium on Information Control Problems in Manufacturing – INCOM 2015 Vol. 48, No. 3, pp. 2109-2114, Elsevier (2015)
[Ho2] Hojda M., Comparison of algorithms for constrained multi-robot task allocation, Advances in Systems Science : proceedings of the International Conference on Systems Science, pp. 255-264, Springer (2017)
[HALG] Hvattum L., Arntzen, H., Lokketangen A., Glover F.: Alternating control tree search for knapsack/covering problems. Journal of Heuristics 16, pp. 239–258. Springer (2008)
[JS] Jung D., Savvides A., An Energy Efficiency Evaluation for Sensor Nodes with Multiple Processors, Radios and Sensor, Proceedings of the 27th IEEE Conference on Computer Communications, pp. 1112–1120 (2008)
[LLFNS] Li X., Lille I., Falcon R., Nayak A., Stojmenovic I., Servicing Wireless Sensor Networks by Mobile Robots, IEEE Communications Magazine, Vol. 50, No. 7, pp. 147–154 (2012)
[MPA] Melodia Tl, Pompili D., Akyildiz I., Handling Mobility in Wireless Sensor and Actor Networks, IEEE Transactions on Mobile Computing, Vol. 10, No. 2, pp. 160–173 (2010)
[RSSH] Rahimi M., Shah H., Sukhatme G., Heideman J., Studying the Feasibility of Energy Harvesting in a Mobile Sensor Network Proceedings of ICRA ‘03. IEEE International Conference on Robotics and Automation, 2003, Vol. 1, pp. 14–19 (2003)
[SBCFTW] Shott B., Bajura M., Czarnaski J., Flidr J., Tho T., Wang L., A modular power-aware microsensor with 1000x dynamic power range, Proceedings of Information Processing in Sensor Networks, pp. 469–474 (2005)
[TI] Tekdas O., Isler V., Using Mobile Robots to Harvest Data from Sensor Fields, IEEE Wireless Communications, Vol. 16, No. 1, pp. 22–28 (2009)
[TLLB] Tirta Y., Li Z., Lu Y-H., Bagchi S., Efficient Collection of Sensor Data in Remote Fields Using Mobile Collectors, Proceedings of 13th International Conference on Computer Communications and Networks, Vol. 50, No. 7, pp. 147–154 (2012)
[YMHC] Yong F., Mo S., Hackmann G., Chenyang L., Practical control of transmission power for Wireless Sensor Networks, Proceedings of 20th IEEE International Conference on Network Protocols, pp. 1–10 (2012)
[glpk] GNU Linear Programming Kit, https://www.gnu.org/software/glpk/
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Hojda, M. (2017). Task allocation for multi-robot teams in dynamic environments. In: Mitkowski, W., Kacprzyk, J., Oprzędkiewicz, K., Skruch, P. (eds) Trends in Advanced Intelligent Control, Optimization and Automation. KKA 2017. Advances in Intelligent Systems and Computing, vol 577. Springer, Cham. https://doi.org/10.1007/978-3-319-60699-6_47
Download citation
DOI: https://doi.org/10.1007/978-3-319-60699-6_47
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-60698-9
Online ISBN: 978-3-319-60699-6
eBook Packages: EngineeringEngineering (R0)