Abstract
Map-based navigation in outdoor terrain lacking man-made structures or other highly distinctive landmarks can produce severe localization problems. This paper presents an approach to navigation which implements high level geometric reasoning and matching strategies based on those used by skilled human navigators. This approach, which is demonstrated on a real example involving imagery of mountainous terrain obtained with a video camera and USGS map data, is designed to avoid many of the pitfalls occurring when an attempt is made to navigate by modeling the environment mathematically. It exploits feature attributes which cannot be easily expressed quantitatively but are central to the successful human navigation process.
Similar content being viewed by others
References
Andreas, R.D., Hostetler, L.D. and Beckmann, R.C. (1978). Continuous Kalman Updating of an Inertial Navigation System Using Terrain Measurements. In Proc. IEEE National Aerospace Electronics Conference (pp. 1263–1270).
Baird, C.A. and Abramson, M.R. (1984). A Comparison of Several Digital Map-Aided Navigation Techniques. In Proc. IEEE Position Location and Navigation Symposium (pp. 294–300).
Bennett, B.H. (1992). A Problem-Solving Approach to the Localization Problem. Ph.D. thesis, University of Minnesota.
Bowditch, N. (1802). American Practical Navigator. Blunt.
Brändli, M. (1996). Hierarchical Models for the Definition and Extraction of Terrain Features. In P.A. Burrogh and A.U. Frank (eds.), Geographic Objects with Indeterminate Boundaries (pp. 257–270). Taylor & Frank.
Brooks, R.A. (1985). Aspects of Visual Map Making. In Proc. IEEE International Conference on Robotics and Automation (pp. 824–829).
Burrough, P.A. (1992). Development of Intelligent Geographic Information Systems, International Journal of Geographic Information Systems 6(1): 1–11.
Clementini, E. and DiFelice, P. (1996). An Algegraic Model for Spatial Objects with Indeterminate Boundaries. In P.A. Burrogh and A.U. Frank (eds.), Geographic Objects with Indeterminate Boundaries (pp. 155–169). Taylor & Frank.
Cohen, S.C., Chinn, D.S., Torrence, M.H. and Dunn, P.J. (1993). Spaceborne Laser Ranging: Sensitivity to Ephereris and Range Measurement Errors, Manuscripta Geodaetica: 72–81.
Cozman, F. and Krotkov, E. (1997). Automatic Mountain Detection and Pose Estimation for Teleoperation of Lunar Rovers. In Proc. IEEE International Conference on Robotics and Automation (pp. 2452–2457). Albuquerque, NM.
Duerr, T.E. (1992). Effect of Terrain Masking on GPS Position dilution of Precision, Navigation (3): 317–323.
Ernst, M.D. and Flinchbaugh, B.E. (1989). Image/Map Correspondence Using Curve Matching. In AAAI Symposium on Robot Navigation (pp. 15–18).
Goyal, R.P. and Egenhofer, M.J. (in press). Cardinal Directions between Extended Spatial Objects. In IEEE Transactions on Knowledge and Data Engineering.
Grimson, W.E.L. (1990). Object Recognition by Computer: The Role of Geometric Constraints. The MIT Press.
Heinrichs, M.R., Montello, D.R., Nusslé, C.M. and Smith, K. (1989). Localization with Topographic Maps. In Proceedings of the AAAI Symposium on Robot Navigation (pp. 29–32).
Heinrichs, M.R., Smith, K., Pick, Jr. H.L., Bennett, B. and Thompson, W. (1992). Strategies for Localization. In Proc. DARPA Image Understanding Workshop (pp. 321–325).
Huttenlocher, D.P. and Ullman, S. (1987). Object Recognition Using Alignment. In Proc. First International Conference on Computer Vision (pp. 102–111).
Kuipers, B. and Levitt, T.S. (1988). Navigation and Mapping in Large-Scale Space, AI Magazine 9(2): 25–43.
Levitt, T.S. and Lawton, D.T. (1990). Qualitative Navigation for Mobile Robots, Artificial Intelligence 44(3): 305–4360.
Mattos, P. (1992). GPS, Electronics and Wireless World: 982–987.
Moravec, H. (1988). Sensor Fusion in Certainty Grids for Mobile Robots, AI Magazine 9(2): 61–74.
Papadias, D. and Egenhofer, M.J. (1997). Algorithms for Hierarchical Spatial Reasoning, GeoInformatica 1(3): 251–273.
Pick, Jr., H.L., Heinrichs, M.R., Montello, D.R., Smith, K., Sullivan, C. and Thompson, W. (1996). Topographic Map Reading. In J. Flach, P. Hancock, J. Caird and K. Vicente (eds.), Ecology of Human-Machine Systems. Lawrence Erlbaum Associates.
Sanso, F. (1973). An Exact Solution of the Roto-Translation Problem, Photogrammetria 29: 203–216.
Schlieder, C. (1995). Reasoning About Ordering. In A.U. Frank and W. Kuhn (eds.), Spatial Information Theory: A Theoretical Basis for GIS (pp. 341–349). Springer.
Stein, F. and Medioni, G. (1992). Map-Based Localization using the Panoramic Horizon. In Proc. IEEE International Conference on Robotics and Automation. Nice, France.
Sutherland, K.T. (1994). The Stability of Geometric Inference in Location Determination. Technical Report UUCS-94–021, University of Utah.
Sutherland, K.T. and Thompson, W.B. (1994). Localizing in Unstructured Environments: Dealing with the Errors. In IEEE Trans. on Robotics and Automation (pp. 740–754).
Talluri, R. and Aggarwal, J.K. (1992). Position Estimation for an Autonomous Mobile Robot in an Outdoor Environment. In IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 8 (pp. 573–584).
Thompson, E.H. (1958). An Exact Linear Solution of the Problem of Absolute Orientation, Photogrammetria 13(4): 163–178.
Tranqulla, J.M. and Al-Rizzo, H.M. (1993). Investigation of GPS Precise Relative Static Positioning During Periods of Ice Clouds and Snowfall Precipitation. In IEEE Trans. Geoscience and Remote Sensing (pp. 295–299).
Valiquette, C.M. (1995). Localization in Outdoor Static Terrain. Master's thesis, University of Utah.
Yacoob, Y. and Davis, L.S. (1991). Computational Ground and Airborne Localization Over Rough Terrain. Technical Report CAR-TR-591, Computer Vision Laboratory, University of Maryland.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Thompson, W.B., Valiquette, C.M., Bennett, B.H. et al. Geometric reasoning under uncertainty for map-based localization. Spatial Cognition and Computation 1, 291–321 (1999). https://doi.org/10.1023/A:1010049703452
Issue Date:
DOI: https://doi.org/10.1023/A:1010049703452