1. On Information Invariants in Robotics.
    B. R. Donald
    Artificial Intelligence 72 (1995) pp. 217-304. [PDF]

    Abstract: We consider the problem of determining the information requirements to perform robot tasks, using the concept of information invariants. This paper represents our attempt to characterize a family of complicated and subtle issues concerned with measuring robot task complexity. We also provide a first approximation to a purely operational theory that addresses a narrow but interesting special case.

    We discuss several measures for the information complexity of a task: (a) How much internal state should the robot retain? (b) How many cooperating agents are required, and how much communication between them is necessary? (c) How can the robot change (side-effect) the environment in order to record state or sensory information to perform a task? (d) How much information is provided by sensors? and (e) How much computation is required by the robot? We consider how one might develop a kind of “calculus” on (a)-(e) in order to compare the power of sensor network systems analytically. To this end, we attempt to develop a notion of information invariants. We develop a theory whereby one sensor network can be “reduced” to another (much in the spirit of computation-theoretic reductions), by adding, deleting, and reallocating (a)-(e) among collaborating autonomous agents.

The following two papers discuss a specific application, in which we removed explicit communication and, instead, harness the ability of (multiple) robots to communicate through the task. The application is moving large objects such as furniture. See Videos also. A key issue is removing synchronization to obtain an asynchronous distributed protocol, using the information invariants formalism above.

  1. Information Invariants for Distributed Manipulation.
    B. R. Donald, J. Jennings, and D. Rus.
    International Journal of Robotics Research, Vol. 16, No. 5 (1997). pp. 673-702. [Postscript, Videos]

  2. Moving Furniture with Teams of Automonous Mobile Robots
    D. Rus, B. R. Donald, and J. Jennings.
    in Proc. IEEE/Robotics Society of Japan International Workshop on Intelligent Robots and Systems, (IROS) Pittsburgh, PA (1995). [Postscript, Videos]

  3. See Videos also.