On The Complexity Of Integrating Spatial Measurements
Thomas Dean · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1989
In this paper, we explore some basic issues concerning the impact of uncertainty on the complexity of map learning: assimilating sensor data to support spatial queries. The primary computational task involves consolidating a set of measurements to support queries concerning the relative position of identifiable locations. We are concerned with the complexity of providing the best possible answers to such queries. We provide a partial categorization of map learning problems according to the sorts of sensors available and the probability distributions that govern their accuracy. The objective of this exercise is to precisely define a set of computational problems and investigate the properties of algorithms that provide solutions to these problems. We show that hard problems involving uncertain measurements arise even in a single-dimensional setting. We also show that there are interesting two-dimensional map learning problems that can be solved in polynomial time. By considering basic time/space tradeoffs, we provide some insight into exactly what makes map learning hard, and how various sensors might be employed to circumvent combinatorial problems.