Distributed control and coordination of autonomous agents in a dynamic, reconfigurable system

• US 6,636,781 B1
• Filed: 05/22/2002
• Issued: 10/21/2003
• Est. Priority Date: 05/22/2001
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Will, Peter, Shen, Wei-Min, Salemi, Behnam
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Marc, McDieunel, Marc, McDieunel
• Application Number:
  US10/155,489
• Time in Patent Office: 517 Days
• Field of Search: 700/245, 700/254, 700/189, 700/100, 700/248-251, 700/262, 700/86, 318/568.11, 703/1, 703/2, 703/7, 701/23, 714/763, 714/764, 714/766, 714/770, 714/772, 403/171-174, 403/176, 522/50, 522/59
• US Class Current: 700/248
• CPC Class Codes: B08B 9/045 the cleaning devices being rotated while moved , e.g. flexible rotating shaft or "snake"B08B9/047 takes precedence
• CPC Class Codes: B25J 9/065 Snake robots
• CPC Class Codes: B25J 9/1617 Cellular, reconfigurable manipulator, e.g. cebot
• CPC Class Codes: G05B 2219/40109 Consider each part to be assembled as an agent, behaving autonomously
• CPC Class Codes: G05B 2219/40302 Dynamically reconfigurable robot, adapt structure to tasks, cellular robot, cebot
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

Systems and techniques are described for distributed control and coordination of autonomous agents in a system. A protocol for distributed control allows autonomous agents to negotiate a group task for the agents, such as locomotion or self-reconfiguration in a robot application, and to synchronize individual agent actions to effect the group task. A protocol for adaptive communication allows autonomous agents, such as physically coupled self-sufficient robot modules, to continuously discover changes in their local topology. In general, in one implementation, the technique includes: discovering a local topology, which includes a type of a communication connection to autonomous agents in the reconfigurable network topology, and determining an action based upon a received control message and the determined local topology.

Claims

1. A method comprising:

discovering a communication connection to autonomous agents communicatively coupled together in a reconfigurable network topology;

determining a local topology including a type of the communication connection;

receiving a control message having content; and

in response to the control message, determining an action based upon the received message content and the determined local topology.

2. The method of claim 1, wherein said determining the communication connection type comprises identifying a first communication port and a second communication port, the first and second communication ports being communicatively coupled by the communication connection.

3. The method of claim 2, wherein said identifying the first and second communication ports comprises identifying orientations of the first and second communication ports with respect to one or more defined references.

4. The method of claim 3, wherein said identifying the orientations of the first and second communication ports comprise:

identifying a first orientation of the first communication port with respect to a first robot module coupled with the first communication port, the first robot module being one of the one or more defined references; and

identifying a second orientation of the second communication port with respect to a second robot module coupled with the second communication port, the second robot module being another of the one or more defined references.

5. The method of claim 2, wherein said determining the action comprises determining whether to perform a locally selected action or no action and determining whether to propagate the control message or to not propagate the control message.

6. The method of claim 5, wherein the communication connection comprises a first communication connection, the method further comprising:

discovering a second communication connection, and said receiving the control message comprises receiving the control message over the second communication connection.

7. The method of claim 6, further comprising propagating the control message to the first communication connection based upon the local topology.

8. The method of claim 7, wherein said propagating the control message comprises:

changing the control message; and

transmitting the changed control message over the first communication connection.

9. The method of claim 7, further comprising performing the locally selected action.

10. The method of claim 2, wherein the control message comprises a first control message, the action comprises a maneuver, and wherein said determining the action comprises:

based upon a locally selected action, the first control message and the local topology, generating a second control message to coordinate collective behavior of the autonomous agents.

11. The method of claim 10, wherein said determining the action further comprises:

transmitting the second control message;

receiving additional control messages to coordinate the collective behavior of the autonomous agents;

resolving conflicts among actions of the autonomous agents, including the locally selected action; and

performing the maneuver.

12. The method of claim 1, further comprising:

before each of a plurality of maneuvers, repeating said discovering a communication connection and said determining a local topology; and

performing the plurality of maneuvers in collaboration with the autonomous agents to effect collective behavior.

13. The method of claim 12, wherein the autonomous agents comprise robot modules coupled together to form a self-reconfigurable robot, and wherein the collective behavior is reconfiguration or locomotion of the self-reconfigurable robot.

14. A robotic system comprising:

a plurality of robot modules in communication with each other and forming a reconfigurable network topology;

each robot module comprising;

one or more actuators to cause movement of the robot module;

a communication interface to send and receive messages to and from the other robot modules, the communication interface forming one or more communication connections; and

a machine-readable medium embodying information indicative of instructions for causing the robot module to perform operations comprising;

sending control signals to the one or more actuators to cause the robot module to perform actions; and

before each of the actions, discovering a local topology including one or more types of the one or more communication connections.

15. The system of claim 14, wherein said discovering the local topology comprises determining mutual communication connection ports used on either side of the one or more communication connections.

16. The system of claim 15, wherein the operations further comprise:

receiving a control message having content; and

in response to the control message, determining a current action based upon the received message content and the determined local topology.

17. The system of claim 14, wherein each robot module further comprises four connectors to physically link the robot module with the other robot modules to create a self-reconfigurable robot.

18. The system of claim 17, wherein the communication interface comprises four optical transceivers to communicatively link the robot module with the other robot modules.

19. The system of claim 17, wherein the messages provide distributed control of the reconfigurable robot by propagating through the reconfigurable robot based upon the discovered local topology to coordinate collective behavior of the reconfigurable robot.

20. The system of claim 19, wherein the collective behavior comprises locomotion of the self-reconfigurable robot.

21. A robot module comprising:

means for coupling with a plurality of robot modules;

means for discovering local topology between each of a plurality of maneuvers; and

means for performing the plurality of maneuvers in collaboration with the plurality of robot modules to effect collective behavior.

22. The robot module of claim 21, wherein the means for coupling comprises four connectors and four optical transceivers.

23. The robot module of claim 21, wherein the means for discovering local topology comprises:

means for establishing an active communication link with another robot module; and

means for determining mutual communication connection ports used on either side of the active communication link.

24. The robot module of claim 21, wherein the means for performing the plurality of maneuvers comprises:

one or more actuators; and

means for generating messages to coordinate the collective behavior by triggering multiple different behaviors in the plurality of robot modules.

25. The robot module of claim 21, wherein the collective behavior comprises reconfiguration of the plurality of robot modules to form a reconfigured network topology.

26. A machine-readable medium embodying information indicative of instructions for causing one or more machines to perform operations comprising:

discovering a communication connection to autonomous agents communicatively coupled together in a reconfigurable network topology;

determining a local topology including a type of the communication connection;

receiving a control message having content; and

in response to the control message, determining an action based upon the received message content and the determined local topology.

27. The machine-readable medium of claim 26, wherein said determining the communication connection type comprises identifying a first communication port and a second communication port, the first and second communication ports being communicatively coupled by the communication connection.

28. The machine-readable medium of claim 27, wherein said identifying the first and second communication ports comprises identifying orientations of the first and second communication ports with respect to one or more defined references.

29. The machine-readable medium of claim 28, wherein said identifying the orientations of the first and second communication ports comprises:

identifying a first orientation of the first communication port with respect to a first robot module coupled with the first communication port, the first robot module being one of the one or more defined references; and

identifying a second orientation of the second communication port with respect to a second robot module coupled with the second communication port, the second robot module being another of the one or more defined references.

30. The machine-readable medium of claim 26, wherein said determining the action comprises determining whether to perform a locally selected action or no action and determining whether to propagate the control message or to not propagate the control message.

31. The machine-readable medium of claim 30, wherein the communication connection comprises a first communication connection, and the operations further comprise:

discovering a second communication connection, and said receiving the control message comprises receiving the control message over the second communication connection.

32. The machine-readable medium of claim 31, wherein the operations further comprise propagating the control message to the first communication connection based upon the local topology.

33. The machine-readable medium of claim 32, wherein said propagating the control message comprises:

changing the control message; and

transmitting the changed control message over the first communication connection.

34. The machine-readable medium of claim 32, wherein the operations further comprise initiating performance of the locally selected action.

35. The machine-readable medium of claim 26, wherein the control message comprises a first control message, the action comprises a maneuver, and wherein said determining the action comprises:

based upon a locally selected action, the first control message and the local topology, generating a second control message to coordinate collective behavior of the autonomous agents.

36. The machine-readable medium of claim 35, wherein said determining the action further comprises:

transmitting the second control message;

receiving additional control messages to coordinate the collective behavior of the autonomous agents;

resolving conflicts among actions of the autonomous agents, including the locally selected action; and

initiating performance of the maneuver.

37. The machine-readable medium of claim 26, wherein the operations further comprise:

before each of a plurality of maneuvers, repeating said discovering a communication connection and said determining a local topology; and

initiating performance of the plurality of maneuvers in collaboration with the autonomous agents to effect collective behavior.

38. The machine-readable medium of claim 37, wherein the autonomous agents comprise robot modules coupled together to form a self-reconfigurable robot, and wherein the collective behavior is reconfiguration or locomotion of the self-reconfigurable robot.