Radhika Nagpal
Assistant Professor
Computer Science
33 Oxford Street, MD 235,
Cambridge, MA
Harvard University

Bio-inspired Multi-agent Models and Theory

• Programmable Self-Assembly inspired by Developmental Biology (Amorphous Computing)
• A Local-to-Global Theory for Asynchronous Cellular Automata

Bio-inspired Distributed Systems

• Modular Robotics and Robot Swarms
  • Collective Construction by Simple Mobile Robots, using Extended Stigmergy
  • Programmable Self-Assembly Algorithms for Modular Robots
  • Environmentally-adaptive Shape Formation on Modular Robots
  • Self-repairing Formation Control for Robot Swarms
  • Ant-inspired Autonomous Microrobot Swarms
• Ad-hoc Wireless Sensor Networks
  • Synchronization and Desynchronization on Wireless Sensor Networks
  • Gradient-based localization on Wireless Sensor Networks

Multi-cellular Systems Biology

• From Cell Division to Network Topology in Epithelial Tissues (Fruitfly).

	Programmable Self-Assembly inspired by Developmental Biology (Amorphous Computing) Cells with identical DNA cooperate to form complex structures, from fruitflies to humans. As part of the Amorphous Computing project, we used inspiration from multicellular development to create several models of self-assembly: (1) Pattern Formation on amorphous cellular automata (2) an Origami-inspired Foldable Programmable Surface (3) a Directed Growth Model inspired by cell growth/death. This work demonstrated how one can build global-to-local compilers: in each case there is a high-level global shape language and a compiler that automatically translates the user-specified global goal into a provable agent ("cell") program, by composing a small set of bio-inspired primitives. We also showed how biological phenomena, such as scale-invariance and regeneration can be directly encoded into the compilation process. Our more recent work in this area, focuses on adapting these ideas for robotics and programmable materials. (project webpage)
	A Local-to-Global Theory for Asynchronous Cellular Automata Given a global task, and given an agent model with limited local state and communication radius, one can ask some important theoretical questions: Does a local rule exist such that the multi-agent system will robustly solve the task? And, what are the minimal agent requirements? We have developed the beginnings of such a theory, in the context of pattern formation tasks on an asynchronous cellular automata. In particular, we have shown a necessary and sufficient condition, called Local Checkability, that not only allows us to answer the question of existence, but also produce minimal state programs for self-repairing pattern formation. This work sheds new light on current approaches to multi-agent self-assembly and also builds a connection between such spatial systems and more traditional computer science theory.
	Collective Construction by Mobile Robots, using Extended Stigmergy Social insects, such as ants and termites, collectively build large and complex structures even though the individuals are small, simple, and expendable. We have developed a family of decentralized algorithms by which simple robots can cooperate to build a large class of user-specified 2D structures. The key aspect is that the robots use the environment (i.e. the blocks) as a means for indirect communication and coordination (Extended Stigmergy). The algorithms are provably robust and deadlock-free, and are closely related to self-assembly in other domains. We have looked at several variants (disassembly and repair, multiple block types, 3D shapes). We have also built several hardware demonstrations using ER1 and Lego robots and writeable RFID tags to implement extended stigmergy. Collective construction has many important potential civilian applications that we hope to explore. (project webpage)
	Programmable Self-Assembly for Modular Robots Modular robots are a type of robot composed of many connected smart modules with computation, sensors, and actuators ("cells"); the modules can cooperate to allow a single robot to flexibly assume many shapes and functions. An important challenge is the design and analysis of decentralized and robust ialgorithms for module cooperation. We have developed several algorithmic approaches for 3D self-assembly on lattice-style and bipartite modular robots. These "global-to-local" algorithms rely on simple, decentralized, and local agent rules. At the same time they are provably correct for large classes of shapes, in the face of variable agent timing. More recently, we have been developing a common framework for studying self-assembly algorithms, to show how algorithms can translate to different agent models, and how algorithms developed in different domains can be compared on a common ground.
	Environmentally-adaptive Shape Formation on Modular Robots Many living systems constantly adapt their shape to the environment through distributed sensing and actions: e.g. the human capillary network adjusts to oxygenation needs, and plants adjust to sunlight. In contrast, most studies of programmable self-assembly focus on static shape goals. Our goal is to understand how we can create multi-agent robotic systems that constantly adapt their shape to the environment in order to solve user-specified goals. We are studying this problem in the context of a multi-modular robot with distributed tilt sensors that must adapt to variable/changing terrains (e.g. self-balancing walkway). We have recently shown a simple self-organizing algorithm, Distributed Homeostasis, that provably solves this problem for large classes of complex goals and complex sensor-actuator networks. This approach is closely related to consensus in biological systems (flocking, firefly synchronization). We are now extending these ideas to adaptation goals with other types of sensors, and exploring practical applications of adaptive materials. (project webpage)
	Synchronization and Desynchronization on Wireless Sensor Networks The spontaneous emergence of synchronization from simple individuals has fascinated scientists for decades: thousands of pacemaker cells synchronize to create a single heartbeat, and firefly swarms synchronize their flashes to form a powerful visual beacon. Our group is interested in the design of simple, self-organizing algorithms for sensor networks, that can easily adapt and repair to errors and changes in topology. We have shown how firefly-inspired synchronization can be adapted for applications on real wireless sensor networks, with message delays, clock skew, and frequent topology changes. We have also shown one can adapt these principles to solve new problems, such as desynchronization, and we have used this to design a self-repairing TDMA scheme for collision-free wireless transmissions. Our group pursues both the theoretical side (how to prove correctness/convergence) and the implementation side (using Berkeley motes), and we collaborate with groups at Harvard and BBN.
	From Cell Division to Network Topology in Epithelial Tissues In a multicellular tissue or organism, understanding the connection between local cell decisions and emergent system-level properties is an important challenge. Our goal is to develop cell-level (agent-level) models to study such questions, in close collaboration with experimental biologists. Our current work is focused on the cell division process in the rapidly-dividing epithelial tissue of the developing fruit fly wing. We developed a mathematical model that showed an unexpected cell-to-tissue relationship -- that a local cell division strategy can strongly regulate the global network topology of cell connections in such a tissue, resulting in a signature equilibrium distribution of cell shapes. This work led to the discovery of a conserved cell shape distribution accross diverse organisms: fruit fly, frog, hydra and even some plants. More recently we have developed computational models that show that there are some necessary conditions to produce the low shape variability seen in these natural systems, and that it may be possible to infer cell division strategies from tissue-level observations. This work has many interesting implications for biology (.g. proliferation in cancer) and also for computer science (network generation).