Skip to main content
SpringerLink
Log in

Generating Goal Configurations for Scalable Shape Formation in Robotic Swarms

  • Conference paper
  • First Online:
Distributed Autonomous Robotic Systems (DARS 2021)

Part of the book series: Springer Proceedings in Advanced Robotics ((SPAR,volume 22))

Included in the following conference series:

Abstract

In this paper, we present an algorithm that automatically encodes a user-defined complex 2D shape to a set of cells on a grid each characterizing a robot currently in the swarm. The algorithm is validated via up to 100 simulated robots as well as up to 100 physical robots. The results show that the goal configurations generated by the algorithm for the swarms with any size are consistent with the input shapes, moreover, it allows the swarm to adapt to the swarm size change quickly and robustly. The supplementary materials for this paper can be found at: https://tinyurl.com/2huc42t6.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 219.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 279.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 279.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Scher, G., Kress-Gazit, H.: Warehouse automation in a day: from model to implementation with provable guarantees. In: IEEE 16th International Conference on Automation Science and Engineering, pp. 280–287. IEEE (2020)

    Google Scholar 

  2. Le Goc, M., Kim, L.H., Parsaei, A., Fekete, J.-D., Dragicevic, P., Follmer, S.: Zooids: building blocks for swarm user interfaces. In: Proceedings of the 29th Annual Symposium on User Interface Software and Technology, pp. 97–109 (2016)

    Google Scholar 

  3. Trüg, S., Hoffmann, J., Nebel, B.: Applying automatic planning systems to airport ground-traffic control – a feasibility study. In: Biundo, S., Frühwirth, T., Palm, G. (eds.) KI 2004. LNCS (LNAI), vol. 3238, pp. 183–197. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30221-6_15

    Chapter  Google Scholar 

  4. Mong-ying, A.H., Kumar, V.: Pattern generation with multiple robots. In: 2006 Proceedings 2006 IEEE International Conference on Robotics and Automation, pp. 2442–2447. IEEE (2006)

    Google Scholar 

  5. Cheah, C.C., Hou, S.P., Slotine, J.J.E.: Region-based shape control for a swarm of robots. Automatica 45(10), 2406–2411 (2009)

    Article  MathSciNet  Google Scholar 

  6. Hsieh, M.A., Kumar, V., Chaimowicz, L.: Decentralized controllers for shape generation with robotic swarms. Robotica 26(5), 691–701 (2008). ISSN 0263-5747

    Article  Google Scholar 

  7. Rubenstein, M., Shen, W.-M.: Scalable self-assembly and self-repair in a collective of robots. In: 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1484–1489. IEEE (2009)

    Google Scholar 

  8. Stoy, K., Nagpal, R.: Self-repair through scale independent self-reconfiguration. In: 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), vol. 2, pp. 2062–2067. IEEE (2004)

    Google Scholar 

  9. Wang, H., Rubenstein, M.: Shape formation in homogeneous swarms using local task swapping. IEEE Trans. Robot. 36, 597–612 (2020)

    Article  Google Scholar 

  10. Rubenstein, M., Shen, W.-M.: A scalable and distributed approach for self-assembly and self-healing of a differentiated shape. In: 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1397–1402. IEEE (2008)

    Google Scholar 

  11. Gauci, M., Nagpal, R., Rubenstein, M.: Programmable self-disassembly for shape formation in large-scale robot collectives. In: Groß, R., et al. (eds.) Distributed Autonomous Robotic Systems. SPAR, vol. 6, pp. 573–586. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-73008-0_40

    Chapter  Google Scholar 

  12. Alonso-Mora, J., Breitenmoser, A., Rufli, M., Siegwart, R., Beardsley, P.: Multi-robot system for artistic pattern formation. In: 2011 IEEE International Conference on Robotics and Automation, pp. 4512–4517. IEEE (2011)

    Google Scholar 

  13. Romanishin, J.W., Gilpin, K., Claici, S., Rus, D.: 3D M-blocks: self-reconfiguring robots capable of locomotion via pivoting in three dimensions. In: 2015 IEEE International Conference on Robotics and Automation, pp. 1925–1932. IEEE (2015)

    Google Scholar 

  14. Yim, M., et al.: Modular self-reconfigurable robot systems [grand challenges of robotics]. IEEE Robot. Autom. Mag. 14(1), 43–52 (2007)

    Article  MathSciNet  Google Scholar 

  15. Cheng, J., Cheng, W., Nagpal, R.: Robust and self-repairing formation control for swarms of mobile agents. In: AAAI, vol. 5 (2005)

    Google Scholar 

  16. Olivier, R., Hanqiang, C.: Nearest neighbor value interpolation. Int. J. Adv. Comput. Sci. Appl. 3(4), 25–30 (2012)

    Google Scholar 

  17. Vaquero, D., Turk, M., Pulli, K., Tico, M., Gelfand, N.: A survey of image retargeting techniques. In: Applications of Digital Image Processing XXXIII, vol. 7798, pp. 779814. International Society for Optics and Photonics (2010)

    Google Scholar 

  18. Zhang, Y.Y., Wang, P.S.-P.: A parallel thinning algorithm with two-subiteration that generates one-pixel-wide skeletons. In: Proceedings of 13th International Conference on Pattern Recognition, vol. 4, pp. 457–461. IEEE (1996)

    Google Scholar 

  19. Fisher, R.: Distance transform. https://tinyurl.com/22uacjz2

  20. Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Q. 2(1–2), 83–97 (1955)

    Article  MathSciNet  Google Scholar 

  21. Wang, H., et al.: Supplementary Materials. https://tinyurl.com/2huc42t6

Download references

Author information

Authors and Affiliations

  1. Northwestern University, Evanston, IL, 60201, USA

    Hanlin Wang & Michael Rubenstein

Authors
  1. Hanlin Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael Rubenstein
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hanlin Wang .

Editor information

Editors and Affiliations

  1. Mechanical Engineering and Science, Kyoto University, Kyoto, Japan

    Fumitoshi Matsuno

  2. Mechanical Systems Engineering, Nagoya University, Nagoya, Japan

    Shun-ichi Azuma

  3. Computer Science and Information Technology, Hokkaido University, Sapporo, Hokkaido, Japan

    Masahito Yamamoto

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Wang, H., Rubenstein, M. (2022). Generating Goal Configurations for Scalable Shape Formation in Robotic Swarms. In: Matsuno, F., Azuma, Si., Yamamoto, M. (eds) Distributed Autonomous Robotic Systems. DARS 2021. Springer Proceedings in Advanced Robotics, vol 22. Springer, Cham. https://doi.org/10.1007/978-3-030-92790-5_1

Download citation

Publish with us

Policies and ethics

Search

Navigation