Abstract
Mission scenarios beyond line of sight or with limited ground control station access require capabilities for autonomous safe navigation and necessitate a continuous extension of existing and potentially outdated information about obstacles. The presented approach is a novel synthesis of techniques for 3D environment perception and global path planning. A locally bounded sensor fusion approach is used to extract sparse obstacles for global incremental path planning in an anytime fashion. During the flight, a stereo camera checks the field of view along the flight path ahead by analyzing depth images. A 3D occupancy grid is built incrementally. To reduce the high data rate and storage demands of grid-type maps, an approximated polygonal world model is created. For a compacted representation, it uses prisms and ground planes. This enables the system to constantly renew and update its knowledge about obstacles. An incremental heuristic path planner uses both a-priori information as well as incremental obstacle updates to assure a collision-free path at any time. Mapping results from flight tests show the functionality of onboard world modeling from real sensor data. Path planning feasibility is demonstrated within a simulation environment considering world model changes inside the vehicle’s field of view.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Adolf, F., Langer, A., de Melo Pontes e Silva, L., & Thielecke, F. (2007). Probabilistic roadmaps and ant colony optimization for UAV mission planning. In 6th IFAC symposium on intelligent autonomous vehicles.
Andert, F., & Goormann, L. (2008). A fast and small 3-d obstacle model for autonomous applications. In IEEE/RSJ international conference on intelligent robots and systems (pp. 2883–2889).
Branicky, M. S., LaValle, S. M., Olson, K., & Yang, L. (2001). Quasi-randomized path planning. In IEEE international conference on robotics and automation (pp. 1481–1487).
Bresenham, J. E. (1965). Algorithm for computer control of a digital plotter. IBM Systems Journal, 4(1), 25–30.
Bruce, J., & Veloso, M. (2007). Real-time randomized motion planning for multiple domains. In RoboCup 2006: Robot Soccer World Cup X (pp. 532–539). Berlin: Springer.
David Ferguson, M. L., & Stentz, A. T. (2005). A guide to heuristic-based path planning. In Proceedings of the international workshop on planning under uncertainty for autonomous systems, international conference on automated planning and scheduling (ICAPS).
Dittrich, J. S., Bernatz, A., & Thielecke, F. (2003). Intelligent systems research using a small autonomous rotorcraft testbed. In 2nd AIAA unmanned unlimited conference, workshop and exhibit.
Eberly, D. (1999). Distance between two line segments in 3d. Tech. rep., Geometric Tools, LLC, http://www.geometrictools.com/.
Ersson, T., & Hu, X. (2001). Path planning and navigation of mobile robots in unknown environments. In IEEE/RSJ international conference on intelligent robots and systems (pp. 858–864).
Garratt, M. A., & Chahl, J. S. (2008). Vision-based terrain following for an unmanned rotorcraft. Journal of Field Robotics, 25(4–5), 284–301.
Green, W. E., Oh, P. Y., & Barrows, G. (2004). Flying insect inspired vision for autonomous aerial robot maneuvers in near-earth environments. In IEEE international conference on robotics and automation (pp. 2347–2352).
Griffiths, S., Saunders, J., & Curtis, A. (2006). Obstacle and terrain avoidance for miniature aerial vehicles. Robotics and Automation Magazine, 13(3), 34–43.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetic, 4(2), 100–107.
Hrabar, S. E. (2006). Vision-based three-dimensional navigation for an autonomous helicopter. Ph.D. thesis, University of Southern California, Los Angeles, CA, USA, adviser-Gaurav Sukhatme.
Hrabar, S. E. (2008). 3d path planning and stereo-based obstacle avoidance for rotorcraft uavs. In IEEE/RSJ international conference on intelligent robots and systems (pp. 807–814).
Hsu, D., Latombe, J. C., & Kurniawati, H. (2006). On the probabilistic foundations of probabilistic roadmap planning. International Journal on Robotics Research, 25(7), 627–643.
Iocchi, L., Konolige, K., & Bajracharya, M. (2000). Visually realistic mapping of a planar environment with stereo. In Seventh international symposium on experimental robotics.
Johnson, E. N., & Schrage, D. P. (2003). The Georgia tech unmanned aerial research vehicle: Gtmax. In AIAA guidance, navigation and control conference.
Konolige, K. (1997). Improved occupancy grids for map building. Autonomous Robots, 4, 351–367.
Langer, A. (2006). Three-dimensional path planning for an unmanned rotorcraft using probabilistic roadmaps. Instituto Tecnológico de Aeronáutica, São José dos Campos.
LaValle, S. M. (2006). Planning algorithms. Cambridge: Cambridge University Press. Also available at http://planning.cs.uiuc.edu/.
Likhachev, M., Gordon, G., & Thrun, S. (2003). Ara*: Anytime a* with provable bounds on sub-optimality. In Advances in neural information processing systems conference. Cambridge: MIT Press.
Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., & Thrun, S. (2005). Anytime dynamic a*: An anytime, replanning algorithm. In AAAI international conference on automated planning and scheduling.
Morales, Y., & Tsubouchi, T. (2007). Gps moving performance on open sky and forested paths. In IEEE/RSJ international conference on intelligent robots and systems (pp. 3180–3185).
Moravec, H. P., & Elfes, A. (1985). High resolution maps from wide angle sonar. In IEEE international conference on robotics and automation (Vol. 2, pp. 116–121).
Okada, K., Kagami, S., Inaba, M., & Inoue, H. (2001). Plane segment finder: Algorithm, implementation and applications. In IEEE international conference on robotics and automation (pp. 2120–2125).
Pettersson, P. O., & Doherty, P. (2006). Probabilistic roadmap based path planning for an autonomous unmanned helicopter. Journal of Intelligent and Fuzzy Systems, 17(4), 395–405.
Plaku, E., Bekris, K. E., Chen, B. Y., Ladd, A. M., & Kavraki, L. E. (2005). Sampling-based roadmap of trees for parallel motion planning. IEEE Transactions on Robotics, 21, 597–608.
Prassler, E., Scholz, J., & Elfes, A. (2000). Tracking multiple moving objects for real-time robot navigation. Autonomous Robots, 8, 105–116.
Praxedes, L. G. (2007). Advanced three-dimensional route planning under complex constraints. Instituto Tecnológico de Aeronáutica, São José dos Campos.
Ramer, U. (1972). An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing, 1(3), 244–256.
Ren, M., Yang, J., & Sun, H. (2002). Tracing boundary contours in a binary image. Image and Vision Computing, 20, 125–131.
Ruffier, F., & Franceschini, N. (2005). Optic flow regulation: the key to aircraft automatic guidance. Robotics and Autonomous Systems, 50, 177–194.
Saunders, J. B., Call, B., Curtis, A., Beard, R. W., & McLain, T. W. (2005). Static and dynamic obstacle avoidance in miniature air vehicles. In AIAA infotech aerospace conference.
Scherer, S., Singh, S., Chamberlain, L., & Saripalli, S. (2007). Flying fast and low among obstacles. In IEEE international conference on robotics and automation (pp. 2023–2029).
Shim, D. H., Chung, H., & Sastry, S. S. (2006). Conflict-free navigation in unknown urban environments. IEEE Robotics and Automation Magazine, 13(3), 27–33.
Thrun, S. (2002). Robotic mapping: A survey. In G. Lakemeyer & B. Nebel (Eds.), Exploring artificial intelligence in the new millennium. San Mateo: Morgan Kaufmann.
Vestka, L. E. K. P., Claude Latombe, J., & Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12, 566–580.
Watanabe, Y., Calisey, A. J., & Johnson, E. N. (2007). Vision-based obstacle avoidance for uavs. In AIAA guidance, navigation, and control conference.
Wu, A. D., Johnson, E. N., & Proctor, A. A. (2005). Vision-aided inertial navigation for flight control. In AIAA guidance, navigation and control conference.
Zufferey, J. C., & Floreano, D. (2005). Toward 30-gram autonomous indoor aircraft: vision-based obstacle avoidance and altitude control. In IEEE international conference on robotics and automation (pp. 2594–2599).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Andert, F., Adolf, F. Online world modeling and path planning for an unmanned helicopter. Auton Robot 27, 147–164 (2009). https://doi.org/10.1007/s10514-009-9134-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-009-9134-y