Distributed matroid-constrained submodular maximization for multi-robot exploration: theory and practice
Tóm tắt
This work addresses the problem of efficient online exploration and mapping using multi-robot teams via a new distributed algorithm for multi-robot exploration, distributed sequential greedy assignment (DSGA), which is based on sequential greedy assignment (SGA). While SGA permits bounds on suboptimality, robots must execute planning steps sequentially. Rather than plan for each robot sequentially as in SGA, DSGA assigns plans to subsets of robots using a fixed number of sequential planning rounds. DSGA retains the same suboptimality bounds as SGA with the addition of a term that describes the additional suboptimality incurred when assigning multiple plans at once. We use this result to extend a single-robot planner based on Monte-Carlo tree search to the multi-robot domain and evaluate the resulting planner in simulated exploration of a confined and cluttered environment. The experimental results show that for teams of 4–32 robots suboptimality due to redundant sensor information introduced in the distributed planning rounds remains small in practice given only two or three distributed planning rounds while providing a 2–8 times speedup over SGA. We also incorporate aerial robots with inter-robot collision constraints and non-trivial dynamics and address subsequent impacts on safety and optimality. Real-time simulation and experimental results for teams of quadrotors demonstrate online planning for multi-robot exploration and indicate that collision constraints have limited impacts on exploration performance.
Tài liệu tham khảo
Atanasov, N.A., Le Ny, J., Daniilidis, K., & Pappas, G.J. (2015). Decentralized active information acquisition: Theory and application to multi-robot SLAM. In Proceedings of the IEEE international conference on robotics and automation, Seattle, WA.
Barbosa, RdP., Ene, A., Nguyen, H.L., & Ward, J. (2016). A new framework for distributed submodular maximization. In Proceedings of the IEEE annual symposium on foundations of computer science, New Brunswick, NJ.
Best, G., Cliff, O. M., Patten, T., Mettu, R. R., & Fitch, R. (2016). Decentralised Monte Carlo tree search for active perception. In Algorithmic foundation robotics. San Francisco, CA
Browne, C., Powley, E., Whitehouse, D., Lucas, S., Cowling, P. I., Rohlfshagen, P., et al. (2012). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43.
Calinescu, G., Chekuri, C., Pal, M., & Vondrák, J. (2011). Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6), 1740–1766.
Charrow, B. (2015). Information-theoretic active perception for multi-robot teams. Ph.D. thesis, University of Pennsylvania.
Charrow, B., Kumar, V., & Michael, N. (2014). Approximate representations for multi-robot control policies that maximize mutual information. Autonomous Robots, 37(4), 383–400.
Charrow, B., Kahn, G., Patil, S., Liu, S., Goldberg, K., Abbeel, P., Michael, N., & Kumar, V. (2015a). Information-theoretic planning with trajectory optimization for dense 3D mapping. In Proceedings of robotics: science and systems, Rome, Italy.
Charrow, B., Liu, S., Kumar, V., & Michael, N. (2015b). Information-theoretic mapping using Cauchy-Schwarz quadratic mutual information. In Proceedings 1990 IEEE international conference on robotics and automation, Seattle, WA.
Chaslot, G. (2010). Monte-Carlo tree search. Ph.D. thesis, Universiteit Maastricht.
Chekuri, C., & Martin, P. (2005). A recursive greedy algorithm for walks in directed graphs. In Proceedings of the IEEE annual symposium on foundations of computer science, pp 245–253.
Choi, H. L., Brunet, L., & How, J. P. (2009). Consensus-based decentralized auctions for robust task allocation. IEEE Transactions on Robotics, 25(4), 912–926.
Corah, M., & Michael, N. (2017). Efficient online multi-robot exploration via distributed sequential greedy assignment. In Proceedings of robotics: science and system, Cambridge, MA.
Corah, M., & Michael, N. (2018). Distributed submodular maximization on partition matroids for planning on large sensor networks. In Proceedings of the IEEE conference on decision and control. Miami, FL (submitted for publication).
Cover, T. M., & Thomas, J. A. (2012). Elements of information theory. New York, NY: Wiley.
Elfes, A. (1989). Using occupancy grids for mobile robot perception and navigation. IEEE Computer Society, 22(6), 46–57.
Filmus, Y., & Ward, J. (2012). A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. In Proceedings of the IEEE annual symposium on foundations of computer science, New Brunswick, NJ.
Gharan, S.O., & Vondrák, J. (2011). Submodular maximization by simulated annealing. In Proceedings of the symposium on discrete algorithms, Philadelphia, PA.
Gharesifard, B., & Smith, S.L. (2017). Distributed submodular maximization with limited information. IEEE Transactions on Control of Network Systems. https://doi.org/10.1109/TCNS.2017.2740625.
Goundan, P. R., & Schulz, A. S. (2007). Revisiting the greedy approach to submodular set function maximization. Optim Online, 1984, 1–25.
Grimsman, D., Ali, M.S., Hespanha, P., & Marden, J.R. (2017). Impact of information in greedy submodular maximization. In Proceedings of the IEEE conference on decision and control, Melbourne, Australia.
Jadidi, M.G., Miro, J.V., & Dissanayake, G. (2015). Mutual information-based exploration on continuous occupancy maps. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Hamburg, Germany.
Jorgensen, S., Chen, R.H., Milam, M.B., & Pavone, M. (2017). The matroid team surviving orienteers problem: Constrained routing of heterogeneous teams with risky traversal. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Vancouver, Canada.
Julian, B. J., Karaman, S., & Rus, D. (2014). On mutual information-based control of range sensing robots for mapping applications. The International Journal of Robotics Research, 33(10), 1357–1392.
Krause, A., & Guestrin, C.E. (2005). Near-optimal nonmyopic value of information in graphical models. In Proceedings of the conference on uncertainty in artificial intelligence, Edinburgh, Scotland.
Krause, A., Singh, A., & Guestrin, C. (2008). Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9, 235–284.
Ladner, R. E., & Fischer, M. J. (1980). Parallel prefix computation. Journal of the ACM (JACM), 27(4), 831–838.
Lauri, M., & Ritala, R. (2016). Planning for robotic exploration based on forward simulation. Robotics and Autonomous Systems, 83, 15–31.
Mahony, R., Kumar, V., & Corke, P. (2012). Multirotor aerial vehicles: Modeling, estimation, and control of quadrotor. IEEE Robotics and Automation Magazine, 19(3), 20–32.
Mirzasoleiman, B., Karbasi, A., Sarkar, R., & Krause, A. (2013). Distributed submodular maximization: Identifying representative elements in massive data. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani & K. Q. Weinberger (Eds.), Procdeedings of the advances in neural information processing systems (Vol. 26, pp. 2049–2057). Stateline, Nevada: Curran Associates, Inc. http://papers.nips.cc/HrBpaper/5039-distributed-submodular-maximization-identifying-reHrBpresentative-elements-in-massivedata.pdf.
Nelson, E., & Michael, N. (2015). Information-theoretic occupancy grid compression for high-speed information-based exploration. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Hamburg, Germany.
Nemhauser, G. L., & Wolsey, L. A. (1978). Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3), 177–188.
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978a). An analysis of approximations for maximizing submodular set functions-I. Mathematics Program, 14(1), 265–294.
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978b). An analysis of approximations for maximizing submodular set functions-II. Polyhedral Combinatorics, 8, 73–87.
Patten, T. (2017). Active object classification from 3D range data with mobile robots. Ph.D. thesis, The University of Sydney.
Quigley, M., Gerkey, B., Conley, K., Faust, J., Foote, T., Leibs, J., et al. (2009). ROS: An open-source robot operating system. In ICRA workshop on open source software, Kobe, Japan
Rawlings, J. B., & Muske, K. R. (1993). The stability of constrained receding horizon control. IEEE Transactions on Automatic Control, 38(10), 1512–1516.
Regev, T., & Indelman, V. (2016). Multi-robot decentralized belief space planning in unknown environments via efficient re-evaluation of impacted paths. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Daejeon, Korea.
Singh, A., Krause, A., Guestrin, C., & Kaiser, W. J. (2009). Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research, 34, 707–755.
Tabib, W., Corah, M., Michael, N., & Whittaker, R. (2016). Computationally efficient information-theoretic exploration of pits and caves. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Daejeon, Korea.
Williams, J.L. (2007). Information theoretic sensor management. Ph.D. thesis, Massachusetts Institute of Technology.
Williams, R.K., Gasparri, A., & Ulivi, G. (2017). Decentralized matroid optimization for topology constraints in multi-robot allocation problems. In Proceedings of the IEEE international conference on robotics and automation, Singapore.
Yamauchi, B. (1997). A frontier-based approach for autonomous exploration. In Proceedings of the international symposium on computer intelligence in robotics and automation, Monterey, CA.
Zhou, T., Ouyang, H., Chang, Y., Bilmes, J., & Guestrin, C. (2017). Scaling submodular maximization via pruned submodularity graphs. Proceedings of Machine Learning Research, 54, 316–324.