Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A motion strategy for exploration driven by an automaton activating feedback-based controllers

  • Published:
Autonomous Robots Aims and scope Submit manuscript

Abstract

This paper addresses the problem of exploring an unknown, planar, polygonal and simply connected environment. To explore the environment, the robot follows the environment boundary. In the first part of this paper, we propose a motion policy based on simple sensor feedback and a complete exploration strategy is represented as a Moore machine. The proposed motion policy is based on the paradigm of avoiding the state estimation; there is a direct mapping from observation to control. We present the theoretical conditions guaranteeing that the robot discovers the largest possible region of the environment. In the second part of the paper, we propose an automaton that filters spurious observations to activate feedback-based controllers. We propose a practical control scheme whose objective is to maintain a desired distance between the robot and the boundary of the environment. The approach is able to deal with imprecise robot’s observations and controls, and to take into account variations in the robot’s velocities. The control scheme switches controllers according to observations obtained from the robots sensor. Our control scheme aims to maintain the continuity of angular and linear velocities of the robot in spite of the switching between controllers. All the proposed techniques have been implemented and both simulations and experiments in a real robot are presented.

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

Access this article

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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26
Fig. 27
Fig. 28
Fig. 29
Fig. 30
Fig. 31
Fig. 32
Fig. 33
Fig. 34
Fig. 35
Fig. 36
Fig. 37
Fig. 38
Fig. 39
Fig. 40
Fig. 41

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Note that this is the configuration space for a translating disc rather than for a rigid body because of rotational symmetry.

  2. A reflex vertex is a polygon vertex of an internal angle greater than \(\pi \).

References

  • Amigoni, F., & Caglioti, V. (2010). An information-based exploration strategy for environment mapping with mobile robots. Robotics and Autonomous Systems, 58(5), 684–699.

    Article  Google Scholar 

  • Amigoni, F., Gasparini, S., & Gini, M. (2006). Building segment-based maps without pose information. Proceedings of the IEEE, 94(7), 1340–1359.

    Article  Google Scholar 

  • Bicchi, A., Casalino, G., & Santilli, C. (1996). Planning shortest bounded-curvature paths for a class of nonholonomic vehicles among obstacles. Journal of Intelligent Robots Systems, 16(4), 387–405.

    Article  Google Scholar 

  • Bicho, E. (2000). Detecting, representing and following walls based on low-level distance sensors. In Proceedings of the international symposium on neural computation, Berlin, Germany.

  • Borenstein, J., & Koren, Y. (1989). Real-time obstacle avoidance for fast mobile robots. IEEE Transactions on Systems, Man, and Cybernetics, 19(5), 1179–1187.

    Article  Google Scholar 

  • De, A., & Koditschek, D. E. (2013). Toward dynamical sensor management for reactive wall-following. In Proceedings of IEEE international conference on robotics and automation, ICRA 2013, Karlsruhe, Germany (pp. 2400–2406).

  • Durrant-Whyte, H., & Bailey, T. (2006). Simultaneous localization and mapping: Part I. IEEE Robotics and Automation Magazine, 13(2), 99–110.

    Article  Google Scholar 

  • Elfes, A. (1987). Sonar-based real world mapping and navigation. IEEE Transactions on Robotics and Automation, 3(3), 249–264.

    Article  Google Scholar 

  • Feder, H., Leonard, J., & Smith, C. (1999). Adaptive mobile robot navigation and mapping. International Journal of Robotics Research, 18(7), 650–668.

    Article  Google Scholar 

  • Gidhar, Y.-A., & Dudek, G. (2016). Modeling curiosity in a mobile robot for long-term autonomous exploration and monitoring. Autonomous Robots, 40(7), 1267–1278.

    Article  Google Scholar 

  • González-Banos, H., & Latombe, J.-C. (2002). Navigation strategies for exploring indoor environments. International Journal of Robotics Research, 21(10–11), 829–848.

    Article  Google Scholar 

  • Hayet, J.-B., Carlos, H., Esteves, C., & Murrieta-Cid, R. (2014). Motion planning for maintaining landmarks visibility with a differential drive robot. Robotics and Autonomous Systems, 4(62), 456–473.

    Article  Google Scholar 

  • Hopcroft, J., Motwani, R., & Ullman, J. (2000). Introduction to automata theory, languages, and computation. London: Pearson Education.

    MATH  Google Scholar 

  • Juliá, M., Gil, A., & Reinoso, O. (2012). A comparison of path planning strategies for autonomous exploration and mapping of unknown environments. Autonomous Robots, 33(4), 427–444.

    Article  Google Scholar 

  • Katsev, M., Yershova, A., Tovar, B., Ghrist, R., & LaValle, S. M. (2011). Mapping and pursuit-evasion strategies for a simple wall-following robot. IEEE Transactions on Robotics, 27(1), 113–128.

    Article  Google Scholar 

  • Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. International Journal of Robotics Research, 5(1), 90–98.

    Article  Google Scholar 

  • Kolling, A., & Carpin, S. (2008). Extracting surveillance graphs from robot maps. In Proceedings of IEEE/RSJ international conference on intelligent robots and systems (pp. 11–19).

  • Kuipers, B., & Byun, Y. (1991). A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Robotics and Autonomous Systems, 8(1–2), 47–63.

    Article  Google Scholar 

  • Laguna, G., Murrieta-Cid, R., Becerra, H. M., Lopez-Padilla, R., & LaValle, S. M. (2014). Exploration of an unknown environment with a differential drive disc robot. In Proceedings of IEEE international conference on robotics and automation (pp. 2527–2533).

  • Lamperski, A. G., Loh, O. Y., Kutscher, B. L., & Cowan, N. J. (2005). Dynamical wall following for a wheeled robot using a passive tactile sensor. In Proceedings of IEEE international conference on robotics and automation, ICRA 2005, Barcelona, Spain (pp. 3838–3843) .

  • Landa, Y., & Tsai, R. (2008). Visibility of point clouds and exploratory path planning in unknown environments. Communications in Mathematical Sciences, 6(4), 881–913.

    Article  MathSciNet  MATH  Google Scholar 

  • Laumond, J.-P., Jacobs, P. E., Taïx, M., & Murray, R. M. (1994). A motion planner for nonholonomic mobile robots. IEEE Transactions on Robotics and Automation, 10(5), 577–593.

    Article  Google Scholar 

  • LaValle, S. M. (2012). Sensing and filtering: A fresh perspective based on preimages and information spaces. In Foundations and trends in robotics series. Now Publishers, Delft, The Netherlands.

  • Lopez-Padilla, R., Murrieta-Cid, R., Becerra, I., Laguna, G., & LaValle, S. M. (2018). Optimal navigation for a differential drive disc robot: A game against the polygonal environment. Journal of Intelligent Robotic Systems, 89(1–2), 211–250.

    Article  Google Scholar 

  • Lopez-Padilla, R., Murrieta-Cid, R., & LaValle, S. M. (2013). Optimal gap navigation for a disc robot. In E. Frazzoli et al., editor, Proceedings of the tenth workshop on the algorithmic foundations of robotics: Springer tracts in advanced robotics, Berlin: Springer (pp. 123–138).

  • Makarenko, A., Williams, B., Bourgault, F., & Durrant-Whyte, H. (2002). An experiment in integrated exploration. In Proceeding of the IEEE/RSJ international conference on intelligent robots and systems, IROS 2002, Lausanne, Switzerland (pp. 534–539).

  • Minguez, J., & Montano, L. (2004). Nearness diagram (nd) navigation: Collision avoidance in troublesome scenarios. IEEE Transactions on Robotics and Automation, 20(1), 45–59.

    Article  Google Scholar 

  • Murphy, L., & Newman, P. (2008). Using incomplete online metric maps for topological exploration with the gap navigation tree. In Proceedings of IEEE international conference on robotics and automation (pp. 2792–2797).

  • Oriolo, G., Vendittelli, M., Freda, L., Troso, G. (2004). The srt method: randomized strategies for exploration. In Proceedings of IEEE international conference on robotics and automation, ICRA 2004, New Orleans, LA, USA, (vol. 5, pp. 4688–4694).

  • Press, W . H., Teukolsky, S . A., Vettering, W . T., & Flannery, B . P. (1994). Numerical recipes in C. Cambridge: Cambridge University Press.

    Google Scholar 

  • Sarmiento, A., Murrieta-Cid, R., & Hutchinson, S. (2009). An efficient motion strategy to compute expected-time locally optimal continuous search paths in known environments. Advanced Robotics, 23(12–13), 1533–1560.

    Article  Google Scholar 

  • Sim, R., & Dudek, G. (2003). Effective exploration strategies for the construction of visual maps. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, IROS 2003, Las Vegas, Nevada, USA (pp. 3224–3231).

  • Sim, R., & Roy, N. (2005). Global a-optimal robot exploration in slam. In Proceedings of IEEE international conference on robotics and automation, ICRA, Barcelona, Spain (pp. 661–666).

  • Taylor, C. J., & Kriegman, D. (1998). Vision-based motion planning and exploration algorithms for mobile robots. IEEE Transactions on Robotics and Automation, 14(3), 417–426.

    Article  Google Scholar 

  • Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic robotics. Cambridge, MA: MIT Press.

    MATH  Google Scholar 

  • Thrun, S., Fox, D., Burgard, W. (1998). Probabilistic mapping of an environment by a mobile robot. In Proceedings of IEEE international conference on robotics and automation, ICRA 1998, Leuven, Belgium (pp. 1546–1551).

  • Toibero, M., Roberti, F., & Carelli, R. (2009). Stable contour-following control of wheeled mobile robots. Robotica, 27(1), 1–12.

    Article  Google Scholar 

  • Toibero, M., Roberti, F., Carelli, R., & Fiorini, P. (2011). Switching control approach for stable navigation of mobile robots in unknown environments. Robotics and Computer-Integrated Manufacturing, 27(2), 558–568.

    Article  Google Scholar 

  • Tovar, B., Murrieta-Cid, R., & LaValle, S. M. (2007). Distance-optimal navigation in an unknown environment without sensing distances. IEEE Transactions on Robotics, 23(3), 506–518.

    Article  Google Scholar 

  • Yamauchi, B. (1997). A frontier-based approach for autonomous exploration. In Proceedings of IEEE international symposium on computational intelligence in robotics and automation, Monterey, CA, USA (pp. 146–151).

Download references

Author information

Authors and Affiliations

  1. Centro de Investigación en Matemáticas, CIMAT, Guanajuato, Mexico

    Edgar Martinez, Rafael Murrieta-Cid & Hector M. Becerra

  2. Iowa State University, Ames, IA, USA

    Guillermo Laguna

  3. CIATEC, León, Mexico

    Rigoberto Lopez-Padilla

  4. Faculty of Information Technology and Electrical Engineering, University of Oulu, Oulu, North Ostrobothnia, Finland

    Steven M. LaValle

Authors
  1. Edgar Martinez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guillermo Laguna
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rafael Murrieta-Cid
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hector M. Becerra
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Rigoberto Lopez-Padilla
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Steven M. LaValle
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rafael Murrieta-Cid.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work was partially funded by CONACYT Projects 220796 and 264896. The authors would also like to acknowledge the financial support of Intel Corporation for the development of this work.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (mp4 11190 KB)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Martinez, E., Laguna, G., Murrieta-Cid, R. et al. A motion strategy for exploration driven by an automaton activating feedback-based controllers. Auton Robot 43, 1801–1825 (2019). https://doi.org/10.1007/s10514-019-09835-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10514-019-09835-6

Keywords

Search

Navigation