Skip to main content
SpringerLink
Log in

Search Methods in Motion Planning for Mobile Robots

  • Conference paper
  • First Online:
Intelligent Systems and Applications (IntelliSys 2021)

Part of the book series: Lecture Notes in Networks and Systems ((LNNS,volume 296))

Included in the following conference series:

Abstract

Mobile robots are used in a variety of applications ranging from domestic robotics to autonomous vehicles. In several applications, it is important to conduct motion planning for robots to find optimal paths with respect to parameters such as space and time. Classical search methods in the literature can be adapted to guide robotic paths and plan the motion of mobile robots. In this work, we explore three methods, namely the deterministic depth-first search and breadth-first search, and the heuristic A* search. We adapt these to the context of mobile robots navigating a maze and accordingly present the deployed algorithms and corresponding experiments with comparisons. These findings are useful in applications where mobile robots are utilized since the optimization of their paths is beneficial in motion planning. We explain applications of this study in areas such as human-robot collaboration (HRC) and unmanned aerial vehicles (UAVs) for motion planning in robotic paths.

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 229.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 299.99
Price excludes VAT (USA)
  • Compact, lightweight 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. Fried, E.D.J., Pa, W.: Robotics and Motion Planning, Department of Computer Science, Stanford University (1999)

    Google Scholar 

  2. Lacombe, J.C.: Robot Motion Planning. Google Books, New York (2012)

    Google Scholar 

  3. Owen-Hill, A.: Back to Basics: Robot Motion Planning Made Easy. RoboDK (2019)

    Google Scholar 

  4. Masumoto, Y.: Global Positioning System, US Patent, Patent No. 5210540 (1993)

    Google Scholar 

  5. Choset, H.: Robotic Motion Planning: A* and D* Search. Carnegie Mellon University School of Computer Science: The Robotics Institute (2007)

    Google Scholar 

  6. Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972)

    Article  MathSciNet  Google Scholar 

  7. Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 4th edn. Pearson Education Inc., Boston (2020)

    MATH  Google Scholar 

  8. Brundy, A., Wallen, L.: Breadth-first search. In: Bundy, A., Wallen, L. (eds.) Catalogue of Artificial Intelligence Tools, Symbolic Computation (Artificial Intelligence). LNCS, p. 13. Springer, Heidelberg (1984). https://doi.org/10.1007/978-3-642-96868-6_25

  9. Khov, T.: Algorithms on Graphs: Let’s talk Depth-First Search (DFS) and Breadth-First Search (BFS), Medium (2020)

    Google Scholar 

  10. Winston, P.: Artificial Intelligence. Addison Wesley, Boston (1992)

    MATH  Google Scholar 

  11. Hart, P.E., Nilsson, N.J., Raphael, B.: . J. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Deter. IEEE Trans. Syst. Sci. Cybern. SSC4 4(2), 100–107 (1968)

    Article  Google Scholar 

  12. Thoben, K.-D., Wiesner, S., Wuest, T.: Industrie 4.0 and smart manufacturing-a review of research issues and application examples. Int. J. Autom. Technol. 11(1), 4–16 (2017)

    Article  Google Scholar 

  13. Tao, F., Qi, Q., Liu, A., Kusiak, A.: Data-driven smart manufacturing. J. Manuf. Syst. 48, 157–169 (2018)

    Article  Google Scholar 

  14. Suchan, J., Bhatt, M.: Commonsense scene semantics for cognitive robotics: towards grounding embodied visuo-locomotive interactions. In: IEEE International Conference on Computer Vision (ICCV) – Workshops, vol. 1, pp. 742–750 (2017)

    Google Scholar 

  15. Conti, C.J., Varde, A.S., Wang, W.: Robot action planning by commonsense knowledge in human-robot collaborative tasks. In: IEEE International IoT, Electronics and Mechatronics Conference (IEMTRONICS), pp. 170–176 (2020)

    Google Scholar 

  16. Conti, C.J., Varde, A.S., Wang, W.: Task quality optimization in collaborative robotics. In: IEEE Big Data Conference, pp. 5652–5654 (2020)

    Google Scholar 

  17. Chen, M., Nikolaidis, S., Soh, H., Hsu, D., Srinivasa, S.: Planning with trust for human-robot collaboration. In: ACM/IEEE International Conference on Human-Robot Interaction (HRI), pp. 307–315 (2018)

    Google Scholar 

  18. Beard, R., et al.: Autonomous vehicle technologies for small fixed-wing UAVs. J. Aerospace Comput. Inf. Commun. 2(1), 92–108 (2005)

    Google Scholar 

  19. Connected Automated Driving Europe, Drone dataset of naturalistic road user trajectories from intersections (2020). https://connectedautomateddriving.eu/

  20. Daponte, P., et al.: A review on the use of drones for precision agriculture. IOP Conf. Ser. Earth Environ. Sci. 275, 012022 (2018)

    Google Scholar 

  21. Persaud, P., Varde, A., Robila, S.: Enhancing autonomous vehicles with commonsense: smart mobility in smart cities. In: IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 1008–1012 (2017)

    Google Scholar 

  22. Scuito, A., Saini, A., Forlizzi, J., Hong, J.: Hey Alexa, What’s Up? A mixed-method studies of in-home conversational agent usage. In: ACM Designing Interactive Systems (DIS) Conference, pp. 857–868 (2018)

    Google Scholar 

  23. Romanov, N., Johnson, C.E., Case, J.P., Goel, D., Gulmann, S., Dooley, M.: Mobile robot for cleaning. US Patent, iRobot Corp., Patent No. US 8,961,695 B2 (2015)

    Google Scholar 

  24. Global Data Technology, Domestic bots are expanding their repertoire but how much value do they bring? (2019). https://www.verdict.co.uk/domestic-robots-2019/

  25. Glover, F., Greenberg, H.: New approaches for heuristic search: a bilateral linkage with artificial intelligence. Eur. J. Oper. Res. 19(2), 119–130 (1989)

    Article  MathSciNet  Google Scholar 

  26. Kanal, L., Kumar, V.: Search in Artificial Intelligence. Google Books, New York (2012)

    MATH  Google Scholar 

  27. Pandey, A., Puri, M., Varde, A.: Object detection with neural models, deep learning and common sense to aid smart mobility. In: IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 859–863 (2018)

    Google Scholar 

  28. Garg, A., Tandon, N., Varde, A.: I am guessing you can’t recognize this: generating adversarial images for object detection using spatial commonsense. In: AAAI Conference on Artificial Intelligence (AAAI), pp. 13789–13790 (2020)

    Google Scholar 

  29. Tang, S.H., Khaksar, W., Ismail, N.B., Ariffin, M.K.A.: A review on robot motion planning approaches. Pertanika J. Sci. Tech. 20(1), 15–29 (2012)

    Google Scholar 

  30. Anand, M.D., Selvaraj, T., Kumanan, S., Johnny, M.A.: Path optimization algorithm for an autonomous mobile robot. Int. J. Appl. Manage. Technol. 4(2), 149–161 (2006)

    Google Scholar 

  31. Sarıel, S., Akın, H.: A novel search strategy for autonomous search and rescue robots. In: Nardi, D., Riedmiller, M., Sammut, C., Santos-Victor, J. (eds.) RoboCup 2004. LNCS (LNAI), vol. 3276, pp. 459–466. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-32256-6_40

    Chapter  Google Scholar 

  32. Hollinger, G., Singh, S., Djugash, J.: Efficient multi-robot search for a moving target. Int. J. Robot. Res. 28(2), 201–219 (2009)

    Article  Google Scholar 

  33. Tandon, N., Varde, A., de Melo, G.: Commonsense knowledge in machine intelligence. ACM SIGMOD Rec. 48(4), 49–52 (2017)

    Article  Google Scholar 

  34. Sap, M., Shwartz, V., Bosselut, A., Choi, Y., Roth, D.: Commonsense reasoning for natural language processing. In: Annual Meeting of the Association for Computational Linguistics (ACL), pp. 27–33 (2020)

    Google Scholar 

  35. Razniewski, S., Tandon, N., Varde, A.: Information to wisdom: commonsense knowledge extraction and compilation. In: ACM International Conference on Web Search and Data Mining (WSDM), pp. 1143–1146 (2021)

    Google Scholar 

  36. Watkins-Valls, D., Xu, J., Waytowich, N.R., Allen, P.K.: Learning your way without map or compass: panoramic target driven visual navigation. In: International Conference on Intelligent Robots and Systems (IROS), pp. 5816–5823 (2020)

    Google Scholar 

  37. Liu, B., Xiao, X., Stone, P.: A lifelong learning approach to mobile robot navigation. IEEE Robot. Autom. Lett. 6(2), 1090–1096 (2021)

    Article  Google Scholar 

Download references

Acknowledgments

Dr. Aparna Varde’s research is supported by a Faculty Scholarship Program from the department of Computer Science, and a Doctoral Faculty Program from the Graduate School, both at Montclair State University. She is also funded by a grant from NSF MRI: Acquisition of a High-Performance GPU Cluster for Research and Education. Award Number 2018575. In addition, this work incurs student funding via Graduate Assistantships from Montclair State University as well.

Author information

Authors and Affiliations

  1. Department of Computer Science, Montclair State University, Montclair, NJ, 07043, USA

    Laura Paulino, Correy Hannum, Aparna S. Varde & Christopher J. Conti

Authors
  1. Laura Paulino
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Correy Hannum
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Aparna S. Varde
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Christopher J. Conti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Aparna S. Varde .

Editor information

Editors and Affiliations

  1. Faculty of Science and Engineering, Saga University, Saga, Japan

    Kohei Arai

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

Paulino, L., Hannum, C., Varde, A.S., Conti, C.J. (2022). Search Methods in Motion Planning for Mobile Robots. In: Arai, K. (eds) Intelligent Systems and Applications. IntelliSys 2021. Lecture Notes in Networks and Systems, vol 296. Springer, Cham. https://doi.org/10.1007/978-3-030-82199-9_54

Download citation

Publish with us

Policies and ethics

Search

Navigation