Some Complexity Aspects of the Control of Mobile Robots

Abstract

In an earlier work it was shown how the length of the specification of a control procedure is affected by the availability of sensory information. In particular, it was shown that this length can be reduced by a factor that depends on the ratio of the size of the entire state space to the size of the set of states for which feedback is locally effective. In this paper we modify this result to explain why landmark-based navigation through a series of intermediary goals can be beneficial from a complexity point of view. We furthermore show how to choose the resolution of the sensors, i.e. the size of the output space, in order to generate control procedures with short description lengths.