Weitere Artikel dieser Ausgabe durch Wischen aufrufen
The online version of this article (https://doi.org/10.1007/s10458-019-09416-y) contains supplementary material, which is available to authorized users.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This paper introduces a method for dynamic fleet mission planning for autonomous mining (in loop-free maps), in which a dynamic fleet mission is defined as a sequence of static fleet missions, each generated using a modified genetic algorithm. For the case of static fleet mission planning (where each vehicle completes just one mission), the proposed method is able to reliably generate, within a short optimization time, feasible fleet missions with short total duration and as few stops as possible. For the dynamic case, in simulations involving a realistic mine map, the proposed method is able to generate efficient dynamic plans such that the number of completed missions per vehicle is only slightly reduced as the number of vehicles is increased, demonstrating the favorable scaling properties of the method as well as its applicability in real-world cases.
Supplementary material 1 (mp4 191808 KB)
Marshall, J. A., Bonchis, A., Nebot, E., & Scheding, S. (2016). Robotics in mining. In B. Siciliano & O. Khatib (Eds.), Springer handbook of robotics (pp. 1549–1576). Heidelberg: Springer. CrossRef
Haviland, D., & Marshall, J. (2015). Fundamental behaviours of production traffic in underground mine haulage ramps. International Journal of Mining Science and Technology, 25, 7–14. CrossRef
Grehl, S., Sastuba, M., Donner, M., Ferber, M., Schreiter, F., Mischo, H., & Jung, B. (2015). Towards virtualization of underground mines using mobile robots—From 3D scans to virtual mines. In Proceedings 23rd international symposium on mine planning and equipment selection (pp. 711–722).
Langdon, M. (2009). Underground vision. Engineering Technology, 4(20), 44–47. CrossRef
Larsson, J., Appelgren, J., & Marshall, J. (2010). Next generation system for unmanned LHD operation in underground mines. In Proceedings of the annual meeting and exhibition of the society for mining, metallurgy and exploration (SME).
Pasternak, M., & Marshall, J. A. (2016). On the design and selection of vehicle coordination policies for underground mine production ramps. International Journal of Mining Science and Technology, 26(4), 623–627. CrossRef
Berglund, T., Brodnik, A., Jonsson, H., Staffanson, M., & Soderkvist, I. (2010). Planning smooth and obstacle-avoiding b-spline paths for autonomous mining vehicles. IEEE Transactions on Automation Science and Engineering., 7(1), 167–172. CrossRef
Abraham, A. T., Ge, S. S., & Tao, P. Y. (2009). A topological approach of path planning for autonomous robot navigation in dynamic environments. In International conference on intelligent robots and systems (IROS) (pp. 4907–4912).
Murano, A., Perelli, G., & Rubin, S. (2015). Multi-agent path planning in known dynamic environments. In International conference on principles and practice of multi-agent systems (pp. 218–231). Springer.
Yu, J., & LaValle, S. M. (2013). Multi-agent path planning and network flow. In E. Frazzoli, T. Lozano-Perez, N. Roy, & D. Rus (Eds.), Algorithmic foundations of robotics X (Vol. 86, pp. 157–173)., Springer tracts in advanced robotics Berlin: Springer. CrossRef
Luna, R., & Bekris, K. E. (2011). Push and swap: Fast cooperative path-finding with completeness guarantees. In Proceedings of the 22nd international joint conference on artificial intelligence (pp. 294–300).
Yan, Z., Jouandeau, N., & Cherif, A. A. (2013). A survey and analysis of multi-robot coordination. International Journal of Advanced Robotic Systems, 10(12), 399. CrossRef
Wang, Q., & Phillips, C. (2014). Cooperative path-planning for multi-vehicle systems. Electronics, 3(4), 636–660. CrossRef
Chen, Y. F., Liu, M., Everett, M., & How, J. P. (2017). Decentralized non-communicating multiagent collision avoidance with deep reinforcement learning. In 2017 IEEE international conference on robotics and automation (ICRA) (pp. 285–292).
Sartoretti, G. A., Kerr, J., Shi, Y., Wagner, G., Kumar, T. S., Koenig, S., et al. (2019). PRIMAL: Pathfinding via reinforcement and imitation multi-agent learning. IEEE Robotics and Automation Letters, 4(3), 2378–2385. CrossRef
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. CrossRef
Wagner, G., & Choset, H. (2011). M*: A complete multirobot path planning algorithm with performance bounds. In 2011 IEEE/RSJ international conference on intelligent robots and systems, (pp. 3260–3267).
Ferner, C., Wagner, G. & Choset, C. (2013). ODrM* optimal multirobot path planning in low dimensional search spaces. In IEEE international conference on robotics and automation, Karlsruhe, Germany, (pp. 3854–3859).
Sharon, G., Stern, R., Felner, A. & Sturtevant, N.R. (2012). Meta-agent conflict-based search for optimal multi-agent path finding. In International symposium on combinatorial search, (pp. 39–40).
Ma, H., & Koenig, S. (2016). Optimal target assignment and path finding for teams of agents. In Proceedings of the 2016 international conference on autonomous agents and multiagent systems (pp. 1144–1152).
Carpin, S., & Pagello, E. (2002). On parallel RRTs for multi-robot systems. In Proceedings of 8th conference on Italian Association for Artificial Intelligence (pp. 834–841).
Zhong, W., Liu, J., & Jiao, L. (2004). A novel genetic algorithm based on multi-agent systems. In M. A. Kłopotek, S. T. Wierzchoń, & K. Trojanowski (Eds.), Intelligent information processing and web mining, advances in soft computing (Vol. 25, pp. 169–178). Berlin: Springer. CrossRef
Van Lon, R. R. S., Branke, J., & Holvoet, T. (2018). Optimizing agents with genetic programming: An evaluation of hyper-heuristics in dynamic real-time logistics. Genetic Programming and Evolvable Machines, 19(1–2), 93–120. CrossRef
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery problems. Journal für Betriebswirtschaft, 58(1), 21–51. CrossRef
Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. Cambridge: MIT Press. MATH
Wahde, M. (2008). Biologically inspired optimization methods (pp. 40–78). Ashurst: WIT Press. MATH
DeJong, K. A. (1975). An analysis of the behavior of a class of genetic adaptive systems. Ph.D. Dissertation, University of Michigan, Ann Arbor.
Luna, R., & Bekris, K. E. (2011). Efficient and complete centralized multi-robot path planning. In International conference on intelligent robots and systems (IROS) (pp. 3268–3275). IEEE/RSJ.
Sajid, Q., Luna, R., & Bekris, K. E. (2012). Multi-agent pathfinding with simultaneous execution of single-agent primitives. In International symposium on combinatorial search (pp. 88–96).
Standley, T. S. (2010). Finding optimal solutions to cooperative pathfinding problems. In Proceedings of the 24th AAAI conference on artificial intelligence (AAAI), Atlanta, Georgia, USA (Vol. 1, pp. 28–29).
Mosteo, A. R., & Montano, L. (2010). A survey of multi-robot task allocation. Technical report. Instituto de Investigación en Ingeniería de Aragón, University of Zaragoza.
Kartal, B., Nunes, E., Godoy, J., & Gini, M. (2016). Monte carlo tree search with branch and bound for multi-robot task allocation. In The IJCAI-16 workshop on autonomous mobile service robots.
Nunes, E., McIntire, M., & Gini, M. (2017). Decentralized multi-robot allocation of tasks with temporal and precedence constraints. Advanced Robotics, 31(22), 1193–1207. CrossRef
- A method for real-time dynamic fleet mission planning for autonomous mining
- Springer US
Neuer Inhalt/© ITandMEDIA