 |
James McLurkin
Assistant Professor
Rice University, Department of Computer Science |
|
|
James McLurkin
Assistant Professor
Rice University, Department of Computer Science |
|
|
Multi-Robot ComputationI believe that multi-robot systems will require a unique theory of computation, distinct from robotics in general, distributed computation, and networked systems, but borrowing ideas from them all. Physical Data StructuresOne of the key components of this new theory is the idea of physical data structures, and a theoretical model of computation that can reason about them. For example, the image sequence and video below shows robots performing a physical bubble sort to arrange themselves in order of ID. In this algorithm, the execution is complete when the robots form a line sorted by their ID. State is stored in the positions of the robots, creating a physical data structure of positions, robot state, and network connectivity. If G is the graph of the communication network, this gives a worst-case running time of O(diam(G)) - the time for a robot to traverse the longest path. For the worst-case configuration, a line in backwards order, the physical running time grows as O(n). Physical Bubble Sort (23,425 KB avi) This video clip shows the bubble line physical bubble sort algorithm arranging the swarm into a line. Because algorithmic progress is inextricably linked to the motion of the robots, traditional models of computation and complexity results for sorting are meaningless. The current state of the execution is stored in the positions of the robots. This physical data structure has "bits" (perhaps robits?) that must be read and stored, and each action incurs some computational cost during execution. Ultimately, we want to understand the configuration complexity: the amount of information stored in a configuration, and the algorithmic cost of reading and writing this information via sensing, communication, and movement. Robot Speed RatioI further explored computational trade-offs with the idea of the robot speed ratio (RSR), a dimensionless metric of robot speed suitable to systems that rely on multi-hop communication. The propagation speed of relayed messages is large, but not infinite, and problems in algorithm execution can arise when the robot speed is a large fraction of the message propagation speed. The message speed is also a limit on robot speed, as any robot moving away from a message source faster than the messages will never receive new information, and cannot execute any algorithm properly. The RSR is the ratio of robot speed to message speed. This definition of speed is platform-independent and captures the relationship between communications usage, robot mobility, and algorithm accuracy, allowing for trade-offs between these quantities at design time. I evaluated eight algorithms that required a correlation between the computational data structures (routing trees and communications broadcasts) and the physical data structure (the poses of the robots). The accuracy of these algorithms decreased as the RSR increased, and most decreased with a similar rate of decay. Further testing on other systems will reveal if this behavior is true in general, if so, the RSR can be used to produce a coarse estimate of algorithm accuracy before execution. Message Speed (1.81MB mpg) The video above shows the message speed on the SwarmBot system. It is around 3.6 m/s, which is not fast enough to assume that messages are infinitely faster than robot speed. The three video clips below show a network-based navigation algorithm at three different RSRs: 0, 0.02, and 0.16. RSR = 0.00 RSR = 0.02 RSR = 0.16 Publications"Measuring the Accuracy of Distributed Algorithms on Multi-Robot Systems with Dynamic Network Topologies" "Dynamic Task Assignment in Robot Swarms" James McLurkin |
