Distributed Path Planning for Collective Transport Using Homogeneous Multi-robot Systems

详细信息    查看全文

• 关键词：Path planning ; Distributed algorithm ; Distributed bellman ; ford algorithm ; Multi ; robot system ; Collective transport
• 刊名：Springer Tracts in Advanced Robotics
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：112
• 期：1
• 页码：151-164
• 全文大小：825 KB
• 参考文献：1.Cheng, C., Riley, R., Kumar, S.P.R, Garcia-Aceves, J.J.: A loop-free extended Bellman-Ford routing protocol without bouncing effect. In: SIGCOMM ’89 Symposium Proceedings on Communications Architectures and Protocols, vol. 19, pp. 224–236 (1989)
  2.Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discr. Math. 86(1–3), 165–177 (1990)
  3.Fabbri, R., Estrozi, L.F.: On Voronoi diagrams and medial axes. J. Math. Imaging Vis. 17, 27–40 (2002)MATH MathSciNet CrossRef
  4.Fekete, S.P., Kamphans, T., Kröller, A., Mitchell, J.S.B., Schmidt, C.: Exploring and triangulating a region by a swarm of robots. In: 14th International Workshop, 2011, and 15th International Workshop, pp. 206–217, Princeton, NJ, USA (2011)
  5.Ford, L., Fulkerson, D., Bland, R.: Flows in Networks, ser, Princeton Landmarks in Mathematics. Princeton University Press, Princeton (2010)
  6.Kamio, S., Iba, H.: Random sampling algorithm for multi-agent cooperation planning. In: IROS, pp. 1265–1270. IEEE (2005)
  7.Kamio, S., Iba, H.: Cooperative object transport with humanoid robots using rrt path planning and re-planning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2608–2613. IEEE (2006)
  8.Kavraki, L., Svestka, P., claude Latombe, J., Overmars, M.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. In: ICRA, pp. 566–580 (1996)
  9.Kleinrock, L., Silvester, J.: Optimum transmission radii for packet radio networks or why six is a magic number. In: Conference Record, National Telecommunications Conference, pp. 4.3.2–4.3.5, Birmingham, Alabama, Dec 1978
  10.LaValle, S.M.: Rapidly-exploring random trees: a new tool for path planning. Computer Science Department, Iowa State University, Technical report (1998)
  11.Mayya, N., Rajan, V.T.: Voronoi diagrams of polygons: a framework for shape representation. J. Math. Imaging Vis. 6(4), 355–378 (1996)MathSciNet CrossRef
  12.McLurkin, J.: Analysis and implementation of distributed algorithms for multi-robot systems. Ph.D. dissertation, MIT, USA (2008)
  13.McLurkin, J., McMullen, A., Robbins, N., Habibi, G., Becker, A., Chou, A., Li, H., John, M., Okeke, N., Rykowski, J., et al.: A robot system design for low-cost multi-robot manipulation. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2014), pp. 912–918. IEEE (2014)
  14.O’Hara, K.J.O., Balch, T.R.: Distributed path planning for robots in dynamic environments using a pervasive embedded network. In: Proceedings of the Thrid International Joint Conference on Autonomous Agent and Multiagent Systems, pp. 1538–1539, July 2004
  15.Parra-González, E.F., Ramírez-Torres, J.G., Toscano-Pulido, G.: A new object path planner for the box pushing problem. In: Electronics, Robotics and Automotive Mechanics Conference: CERMA’09, pp. 119–124. IEEE (2009)
  16.Reina, A., Di Caro, G.A., Ducatelle, F., Gambardella, L.M.: Distributed motion planning for ground objects using a network of robotic ceiling cameras. In: Towards Autonomous Robotic Systems, pp. 137–148. Springer (2011)
  17.Yamashita, A., Arai, T., Ota, J., Asama, H.: Motion planning of multiple mobile robots for cooperative manipulation and transportation. IEEE Trans. Robot. Autom. 19, 223–237 (2003)CrossRef
  
• 作者单位：Golnaz Habibi (5)
  William Xie (6)
  Mathew Jellins (7)
  James McLurkin (5)
  
  5. Department of Computer Science, Rice University, Houston, TX, USA
  6. Department of Computer Science, University of Texas at Austin, Austin, TX, USA
  7. Purdue University, West Lafayette, IN, USA
  
• 丛书名：Distributed Autonomous Robotic Systems
• ISBN：978-4-431-55879-8
• 刊物类别：Engineering
• 刊物主题：Automation and Robotics
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1610-742X

文摘

We present a scalable distributed path planning algorithm for transporting a large object through an unknown environment using a group of homogeneous robots. The robots are randomly scattered across the terrain and collectively sample the obstacles in the environment in a distributed fashion. Given this sampling and the dimensions of the bounding box of the object, the robots construct a distributed configuration space. We then use a variant of the distributed Bellman-Ford algorithm to construct a shortest-path tree using a custom cost function from the goal location to all other connected robots. The cost function encompasses the work required to rotate and translate the object in addition to an extra control penalty to navigate close to obstacles. Our approach sets up a framework that allows the user to balance the trade-off between the safety of the path and the mechanical work required to move the object. The path is optimal given the sampling of the robots and user input parameters. We implemented our algorithm in both simulated and real-world environments. Our approach is robust to the size and shape of the object and adapts to dynamic environments.