Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Geometric reasoning under uncertainty for map-based localization

  • Published:
Spatial Cognition and Computation

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.

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

Access this article

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.

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.

    Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Google Scholar 

  • Levitt, T.S. and Lawton, D.T. (1990). Qualitative Navigation for Mobile Robots, Artificial Intelligence 44(3): 305–4360.

    Google Scholar 

  • 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.

    Google Scholar 

  • Papadias, D. and Egenhofer, M.J. (1997). Algorithms for Hierarchical Spatial Reasoning, GeoInformatica 1(3): 251–273.

    Google Scholar 

  • 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.

    Google Scholar 

  • 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).

    Google Scholar 

  • Thompson, E.H. (1958). An Exact Linear Solution of the Problem of Absolute Orientation, Photogrammetria 13(4): 163–178.

    Google Scholar 

  • 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.

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1010049703452

Navigation