Abstract
A method of analyzing three-dimensional data such as might be produced by stereo vision or a laser range finder in order to plan a path for a vehicle such as a Mars rover is described. In order to produce robust results from data that is sparse and of varying accuracy, the method takes into account the accuracy of each data point, as represented by its covariance matrix. It computes estimates of smoothed and interpolated height, slope, and roughness at equally spaced horizontal intervals, as well as accuracy estimates of these quantities. From this data, a cost function is computed that takes into account both the distance traveled and the probability that each region is traversable. A parallel search algorithm that finds the path of minimum cost also is described. Examples using real data are presented.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Brooks, R. 1982. Solving the find-path problem by representing free space as generalized cones. Massachusetts Institute of Technology, Cambridge, MA, AI Memo 674.
Brooks, R. 1986. A robust layered control system for a mobile robot. IEEE Journal of Robotics and Automation, RA-2:14–23.
Doshi, R.S., Lam, R.K., and White, J.E. 1988. Region based route planning: Multi-abstraction route planning based on intermediate level vision processing. In Proc. Sensor Fusion: Spatial Reasoning and Scene Interpretation, SPIE, Cambridge, MA.
Duda, R.O. and Hart, P.E. 1973. Pattern Classification and Scene Analysis, Wiley.
Feder, H.J.S. and Slotine, J.-J.E. 1997. Real-time path planning using harmonic potentials. In Proc. IEEE International Conference on Robotics and Automation, Albuquerque, NM, pp. 874–881.
Gat, E., Slack, M.G., Miller, D.P., and Firby, R.J. 1990. Path planning and execution monitoring for a planetary rover. In Proc. IEEE International Conference on Robotics and Automation, Cincinnati, OH, pp. 20–25.
Gennery, D.B. 1979. Object detection and measurement using stereo vision. In Proc. Sixth International Joint Conference on Artificial Intelligence, Tokyo, Japan, pp. 320–327.
Gennery, D.B. 1980. Modelling the environment of an exploring vehicle by means of stereo vision, AIM-339 (Computer Science Dept. Report STAN-CS–80–805), Stanford University.
Gennery, D.B. 1989. Visual terrain matching for a mars rover. In Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Diego, CA, pp. 483–491.
Gennery, D.B. 1991. Planning the route of a robotic land vehicle. NASA Tech Briefs, 15(3).
Giralt, G., Sobek, R., and Chatila, R. 1979. A Multi-level planning and navigation system for a mobile robot: A first approach to hilare. In Proc. Sixth International Joint Conference on Artificial Intelligence, Tokyo, Japan, pp. 335–337.
Hebert, M.H., Kanade, T., and Kweon, I. 1988. 3-D vision techniques for autonomous vehicles, CMU-RI-TR–88–12, Carnegie Mellon University, Pittsburgh, PA.
Holmes, K.G., Wilcox, B.H., Cameron, J.M., Cooper, B.K., and Salo, R.A. 1986. Robotic vehicle computer aided remote driving, Vol. 1, JPL internal report D-3282, Jet Propulsion Laboratory, Pasadena, CA.
Mankins, J.C. (Ed.) 1987. Proc. Mars Rover Technology Workshop. JPL internal report D-4788, Jet Propulsion Laboratory, Pasadena, CA.
Matthies, L., Gat, E., Harrison, R., Wilcox, B., Volpe, R., and Litwin, T. 1995a. Mars microrover navigation: Performance evaluation and enhancement. Autonomous Robots, 2:291–311.
Matthies, L., Litwin, T., and Kelly, A. 1995b. Obstacle detection for unmanned ground vehicles: A progress report. International Symposium of Robotics Research, Munich, Germany.
Matthies, L., Olson, C., Tharp, G., and Laubach, S. 1997. Visual localization methods for mars rovers using lander, rover, and descent imagery. International Symposium on Artificial Intelligence, Robotics, and Automation in Space (i-SAIRAS), Tokyo, Japan.
Mikhail, E.M. (with contributions by F. Ackermann) 1976. Observations and Least Squares, Harper and Row.
Moravec, H.P. 1980. Obstacle avoidance and navigation in the real world by a seeing robot rover, AIM-340 (Computer Science Dept. Report STAN-CS–80–813), Stanford University.
Moravec, H.P. 1988. Sensor fusion in certainty grids for mobile robots. AI Magazine, 9(2):61–74.
Nilsson, N.J. 1971. Problem-Solving Methods in Artificial Intelligence, McGraw-Hill.
Randolph, J.R. (Ed.) 1986. Mars rover 1996 mission concept, JPL internal report D-3922, Jet Propulsion Laboratory, Pasadena, CA.
Ratering, S. and Gini, M. 1995. Robot navigation in a known environment with unknown moving obstacles. Autonomous Robots, 1:149–165.
Roberts, B. and Bhanu, B. 1992. Inertial navigation sensor integrated motion analysis for autonomous vehicle navigation. Journal of Robotic Systems, 9:817–842.
Shirley, D. and Matijevic, J. 1995. Mars pathfinder microrover. Autonomous Robots, 2:283–289.
Slack, M.G. and Miller, D.P. 1987. Path planning through time and space in dynamic domains. In Proc. Tenth International Joint Conference on Artificial Intelligence, Milan, Italy, pp. 1067–1070.
Stentz, A. and Hebert, M. 1995. A complete navigation system for goal acquisition in unknown environments. Autonomous Robots, 2:127–145.
Stephens, M.J., Blissett, R.J., Charnley, D., Sparks, E.P., and Pike, J.M. 1989. Outdoor vehicle navigation using passive 3D vision. In Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Diego, CA, pp. 556–562.
Thorpe, C.E. 1984. Path relaxation: Path planning for a mobile robot. In Proc. National Conference on Artificial Intelligence (AAAI-84), Austin, TX, pp. 318–321.
Weisbin, C.R., Montenerlo, M., and Whittaker, W. 1992. Evolving directions in NASA's planetary rover requirements and technology. In Missions, Technologies and Design of Planetary Mobile Vehicles, Centre National d'Etudes Spatiales, France.
Wilcox, B.H. and Gennery, D.B. 1987. A mars rover for the 1990's. Journal of the British Interplanetary Society, 40:483–488.
Witkowski, C.M. 1983. A parallel processor algorithm for robot route planning. In Proc. Eighth International Joint Conference on Artificial Intelligence, Karlsruhe, West Germany, pp. 827–829.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gennery, D.B. Traversability Analysis and Path Planning for a Planetary Rover. Autonomous Robots 6, 131–146 (1999). https://doi.org/10.1023/A:1008831426966
Issue Date:
DOI: https://doi.org/10.1023/A:1008831426966