Information Invariants for Distributed Manipulation

Abstract

In Donald (1995), we described a manipulation task for coop erating mobile robots that can push large, heavy objects. There, we asked whether explicit local and global communication between the agents can be removed from a family of pushing protocols. In this article, we answer in the affirmative. We do so by using the general methods of Donald (1995), analyzing information invariants.

We discuss several measures for the information complexity of the task: (1) How much internal state should the robot retain? (2) How many cooperating agents are required, and how much communication between them is necessary? (3) How can the robot change (side effect) the environment to record state or sensory information for performing a task? (4) How much information is provided by sensors? and (5) How much computation is required by the robot? To answer these questions, we develop a notion of information invariants. We develop a technique whereby one sensor can be constructed from others by adding, deleting, and reallocating 1) through 5), among collaborating autonomous agents. We add a resource to measures 1) through 5) and ask: 6) How much information is provided by the task mechanics? By answering this question, we hope to develop information invariants that explicitly trade- off resource 6) with resources 1) through 5). The protocols

we describe here have been implemented in several different forms, and we report on experiments to measure and analyze information invariants using a pair of cooperating mobile robots for manipulation experiments in our laboratory.

Get full access to this article

View all access options for this article.

References

Blum, M. , and Kozen, D. 1978 (Ann Arbor, MI). On the power of the compass (or, why are mazes easier to search than graphs?). In Proceedings of the 19th Symposium on the Foundations of Computer Science. Los Alamitos, CA: IEEE Computer Society Press, pp. 132-142.

Briggs, A. 1987. An efficient algorithm for one-step compliant motion planning with uncertainty. Algorithmica 8(2): 195-208.

Canny, J. 1989 (Scottsdale, AZ). On computability of fine motion plans. In Proceedings of the 1989 IEEE International Conference on Robotics and Automation, pp. 1178-1184.

Canny, J. , and Reif, J. 1987. New lower bound techniques for robot motion planning problems . In Proceedings of the 28th Symposium on the Foundations of Computer Science. Los Alamitos, CA : IEEE Computer Society Press, pp. 132-142.

Donald, B. 1989. Error Detection and Recovery in Robotics, vol. 336 of Lecture Notes in Computer Science. New York: Springer-Verlag.

Donald, B.R. 1990. The complexity of planar compliant motion planning with uncertainty. Algorithmica 5(3):353-382.

Donald, B.R. 1992. Robot motion planning. IEEE Trans. Robot. Automat. 8(2):353-382.

Donald, B.R. 1993 (Atlanta, GA). Information invariants in robotics, parts I and II. In Proceedings of the 1993 IEEE International Conference on Robotics and Automation, pp. 116-121.

Donald, B.R. 1995. Information invariants in robotics. Art. Intell. J. 72:217-304.

10.

Donald, B.R. , and Jennings, J. 1992. Constructive recognizability for task-directed robot programming . J. Robot. Autonomous Sys. 9(1):41-74.

11.

Donald, B.R. , Jennings, J. , and Rus, D. 1993a (Chambery, France). Experimental information invariants for cooperating autonomous mobile robots. In Proceedings of the 1993 International Joint Conference on Artificial Intelligence, Workshop on Dynamically Interacting Robots

12.

Donald, B.R. , Jennings, J. , and Rus, D. 1993b (Hidden Valley, PA). Towards a theory of information invariants for cooperating autonomous robots. In Proceedings of the 1993 International Symposium on Robotics Research

13.

Erdmann, M. 1986. Using backprojections for fine motion planning with uncertainty . Int. J. Robot. Res. 5(1):431-459.

14.

Erdmann, M. 1989. On probabilistic strategies for robot tasks. Technical Report AI-TR 1155, Massachusetts Institute of Technology, Artificial Intelligence Laboratory.

15.

Erdmann, M. 1993a (Atlanta, GA). Action subservient sensing and design. In Proceedings of the 1993 IEEE International Conference on Robotics and Automation, vol. 2, New York, NY: Springer-Verlag , pp. 592-598.

16.

Erdmann, M. 1993b. Randomization for robot tasks: using dynamic programming in the space of knowledge states. Algorithmica 10(2/3/4):248-291.

17.

Erdmann, M.A. , and Mason, M.T. 1988. An exploration of sensorless manipulation. IEEE J. Robot. Automat. 4(4):369-379.

18.

Erdmann, M. , Mason, M. , and Vanecek, G. 1993. Mechanical parts orienting: the case of a polyhedron on a table. Algorithmica 10(2/3/4):226-247.

19.

Goldberg, K. 1993. Orienting parts without sensors. Algorithmica 10(2/3/4):201-225.

20.

Hopcroft, J.E. , Schwartz, J. , and Sharir, M. 1984. On the complexity of motion planning for multiple

21.

independent objects: P-space hardness for the "ware-houseman's problem." Int. J. Robot. Res. 3(4):76-88.

22.

Horswill, I. 1995. Analysis of adaptation and environment. Art. Intell. J. 73(1/2):1-30.

23.

Jennings, J. , and Rus, D. 1993 (Oxford, England). Active model acquisition for near-sensorless manipulation with mobile robots. In Hamza, M. H. (ed.): IASTED International Conference on Robotics and Manufacturing. Anaheim, CA: ACTA Press, pp. 179-184.

24.

Kozen, D. 1979. Automata and planar graphs. Fundamentals of Computing Theory, Proceedings of the Conference on Algebraic, Arithmetic and Categorical Methods in Computer Science

25.

Lozano-Pérez, T. , Mason, M.T. , and Taylor, R.H. 1984. Automatic synthesis of fine-motion strategies for robots . Int. J. Robot. Res. 3(1):3-24.

26.

Mason, M.T. 1986. Mechanics and planning of manipulator pushing operations . Int J. Robot. Res. 5(3):53-71.

27.

Mason, M. , and Lynch, K. 1989. Dynamic manipulation. In Proceedings of the 1993 IEEE/RSJ International Symposium on Intelligent Robot Systems . Los Alamitos, CA: IEEE Computer Society Press.

28.

Natarajan, B.K. 1988. On planning assemblies. In Proceedings of the 4th Annual Symposium on Computational Geometry ACM Press, pp. 229-308.

29.

Peshkin, M. 1986. Planning robotic manipulation strategies for sliding objects. PhD Thesis, Carnegie-Mellon University, Pittsburgh, PA.

30.

Rees, J.A. , and Donald, B.R. 1992 (Nice, France). Program mobile robots in scheme. In Proceedings of the 1992 IEEE International Conference on Robotics and Automation. Los Alamitos, CA : IEEE Computer Society Press.

31.

Reif, J. 1979. Complexity of the mover's problem and generalizations . In Proceedings of the 20th Symposium on the Foundations of Computer Science. Los Alamitos, CA: IEEE Computer Society Press.

32.

Rosenschein, S.J. 1989. Synthesizing information-tracking automata from environment descriptions. Technical Report 2, Teleos Research, Palo Alto, CA.

33.

Rus, D. 1992. Fine motion planning for dexterous manipulation. PhD Thesis , Cornell University, Department of Computer Science, Ithaca, NY.

34.

Rus, D. , Donald, B.R. , and Jennings, J. 1995 (Pittsburgh, PA). Moving furniture with mobile robots. In Proceedings of Intelligent Robot Systems, pp. 235-242.