Project AbstractIn problems such as area exploration or search & rescue, a multi-robot system often offer obvious advantages over a single-agent system due to its ability to divide a large, complex mission into smaller, simpler tasks, which can then be carried out by distributed agents often without sophisticated sensors or actuators. In these multi-agent robotic systems, however, the main challenge lies in the problem of combining local rules for individual agents to form global behaviors as a group in a predefined and stable manner. Previous works on Motion Description Languages (MDLs) 123 and Communication and Control Languages (CCLs) 4 attempted to specify robot tasks in a formal environment and focus on the individual dynamics, although it has been seen that this approach is not appealing from a networked point of view as they do not account for the local network topology associated with each robot. Graph Grammars, introduced by Klavins, Ghrist, and Lipsky 5, provides a natural tool for characterizing local interactions and control laws by explicitly focusing on combinatorial interaction rules rather than agent dynamics and geometric interaction conditions, thus providing a framework in which complex, decentralized control strategies can be implemented.
Embedded Graph Grammar based methods specific to multi-agent coordination have been presented in 6, and previously in the GRITS lab, algorithms were developed to determine if a mobile robot network with a predefined sensor and communication range can persistently achieve a specified formation, that is, whether the multi-agent formations can be preserved by the direct maintenance of a subset of inter-agent distances 7. In addition, graph operations were developed to describe agent interactions that implement a given formation, and if persistent, can automatically generate a sequence of such operations.
This research project aims to continue the efforts in extending the current Embedded Graph Grammar framework by developing additional control laws and protocols, in particular, methods for the automatic generation of graph grammars from persistent graphs. By extending the pervious persistent graph algorithm from the automatic generation of graph operations to graph grammars and control laws, graph grammars and control modes can be combined in a hybrid fashion. Once a comprehensive framework is completed, the resulting system will then be implemented on a swarm of iRobot Create robots equipped with GPS as well as wireless communication.
M. Egerstedt and R. Brockett, “Feedback can reduce the specification complexity of motor programs,” IEEE Transactions on Automatic Control, vol. 48, no. 2, pp. 213–223, Feb. 2003.
R. W. Brockett, “On the computer control of movement,” in IEEE International Conference on Robotics and Automation, New York, Apr 1988, p. 534540. V. Manikonda, P. S. Krishnaprasad, and J. Hendler., Mathematical Control Theory. Springer, 1998, ch. ”Languages, Behaviors, Hybrid Architectures and Motion Control”, pp. 199–226. E. Klavins, “A language for modeling and programming cooperative control systems,” in IEEE International Conference on Robotics and Automation, 2004. E. Klavins, R. Ghrist, and D. Lipsky, “Graph grammars for self-assembling robotic systems,” in IEEE Interational Conference on Robotics and Automation, 2004. B. Smith, J. McNew, M. Egerstedt, A. Howard, and E. Klavins, “Multi-Robot Coordination: From High-Level Specifications to Deployed Systems” in IEEE/RSJ International Conference on Intelligent Robots and Systems, 2007 B. Smith, M. Egerstedt, and A. Howard, “Automatic Generation of Persistent Formations for Multi-Agent Networks Under Range Constraints” in International Conference on Networked Robots, 2007.
These details are provided for information only. No information here is legal advice and should not be used as such.