Aaron T. Becker University of Houston, Houston, TX, United States
Roboticists, biologists, and chemists are now producing large populations of simple robots, but controlling large populations of robots with limited capabilities is difficult, due to communication and onboard-computation constraints. This chapter provides controllability proofs for control of mobile robots that move in a 2D workspace where each robot receives exactly the same control inputs.
We focus on two types of control: when control inputs are the desired angular and linear velocity for the robots, and secondly when control inputs are the desired direction and speed for the robots. Both use broadcast control inputs: the first uses control inputs specified in the local reference frame of each robot, while the second uses control inputs specified in the global reference frame. Each method allows steering each robot to a desired goal location in time, but the second option enables a class useful of swarm manipulation tasks to be accomplished efficiently.
Microrobot; Nanorobot; Global inputs; Nonprehensile; Under actuation
Micro- and nanorobotics hold great promise for precision material delivery and for micro construction. According to Sitti et al. “One of the highest potential scientific and societal impacts of small-scale (millimeter and submillimeter size) untethered mobile robots would be their healthcare and bioengineering applications” [1].
The flagship application for precision delivery is targeted therapy [2–6]. The current dominant practice in cancer treatment uses chemotherapy applied systemically, but has associated collateral damage to hair follicles and other fast-growing tissue. Successful precision delivery would steer toxins directly to tumors.
Health care is also a driver for micro construction, which includes minimally invasive surgery [7–10], and tissue engineering [11–15]. The surgical industry is rapidly switching to minimally invasive surgery, which places surgical instruments at the end of long, slender kinematic chains and inserts this apparatus through small incisions, called ports, in the body. There is a desire to shrink the size and number of ports, but as the ports decrease in size, the kinematic chain to the external world becomes less rigid. This flexibility makes dexterity difficult and limits surgical forces.
Long before the advent of minimally invasive surgery, authors dreamed of doing away with incisions and kinematic chains by shrinking the surgeon and tools into a compact submarine-like vehicle that could be piloted through the many fluid-filled lumens of the body. This dream is in its infancy. There has been notable progress with pill cameras, tiny cameras that record a passage through the digestive track, from swallowing to expelling.
Shrinking the surgeon to make a capable autonomous robot is hard for two main limitations: power and computation. As the length of the axis ℓ decreases, the surface area decreases as , but the volume at . This relationship is plotted in Fig. 1.1. Nanocars are perhaps the smallest possible robots, but at 1.4×1.7 nm they are smaller than the smallest transistors currently in production (14 nm, beginning in 2014 by Intel). This limited volume effectively prevents onboard computation in nanorobots and severely limits computation in microrobots. Power is limited for the same reason because stored power is also a function of volume.
In the 2014 Disney movie Big Hero 6, the protagonist Hiro offers a profound view into the future by manufacturing a swarm of 105 microbots. Hiro controls them to self-assemble, build structures, and transport goods and materials. While the “microrobots” of the film are fantasy, the ideas are rooted in reality. Today, micro- and nanorobots can be produced in extremely large quantities. Once a manufacturing process is developed, the marginal cost of producing one additional robot is small. Microrobots can be fabricated using microelectromechanical system (MEMS) techniques, e.g. scratch-drive microrobots [16–19]. These robots are 60 by 250 microns in size, and can be mass-produced with many robots tiled on a single silicon wafer. Perhaps the best examples of large populations are robotic nanocars—synthetic molecules with integrated axles, rolling wheels, and light-driven molecular motors, that are 1.4×1.7 nm in size [20–30]. These are routinely produced in tremendous quantities—a batch the size of an aspirin tablet contained nanocars [21]. This dwarfs the number of automobiles produced in the history of the world—90 million automobiles were manufactured in 2014 [31]. Also, biological agents such as bacteria [3,32–35] and paramecium [36,37] can be grown to achieve large swarms.
Ideally, we would design a system that would allow each robot to be controlled individually. However, next-generation micro- and nanorobotic systems have minimal onboard processing and communications bandwidth. The lack of significant onboard computation makes autonomous operation infeasible. Sending individual control signals to each robot requires communications bandwidth that scales with population sizes. Because these systems are only useful when their populations are immense, the bandwidth required for individual unit control is impractical.
Instead, this chapter focuses on systems with uniform control inputs. Some representative systems are shown in Fig. 1.2: light-driven nanocars are uniformly actuated by a certain wavelength of light, scratch-drive microrobots are uniformly actuated by varying the electric potential across a substrate, and multi-robot systems are uniformly controlled by a broadcast radio signal. Other uniform input examples include the magnetic resonant microrobots of Tung et al. [42]; the magnetic helical swimming micro- and nanorobots of Ghosh and Fischer [43], Tottori et al. [44], and Schürle and Nelson et al. [45,46]; the magnetic microparticles of Diller and Floyd et al. [47–49]; the magnetic milli-scale capsules of Vartholomeos et al. [50]; the magnetic particles studied by Snezhko et al. and Orduño et al. [51–54]; and the tumbling magnetic microrobots of [55]. Biological examples include the electric-field controlled paramecium studied by Hashimoto et al. [36] and Hasegawa et al. [37], the electrokinetic and optically controlled bacteria demonstrated by Steager et al. [32], the magnetic-field controlled bacteria demonstrated by Martel et al. [3,33–35] and magnetic-field steered protozoa demonstrated by Ou et al. [56]. Fig. 1.3 shows an example of bacteria steered by a global control input provided by an external magnetic field.
A swarm of robots controlled by a 2 DoF (degree of freedom) signal is inherently under-actuated since each robot has 2 to 6 DoF. To make robots behave differently requires a mechanism to break symmetry from the control input. Breaking symmetry enables the same control input to steer individual robots to different locations.
Our previous work applied ensemble control theory [58–69] and control Lyapunov functions [70] to steer swarms of robots. Our work [39,41,57,71–77] applied these techniques to steer swarms of single-celled organisms using an external magnetic field [41], because they enabled swarms of robots to be asymptotically driven toward goal states—see overview in Fig. 1.3. On a larger scale, but using similar control laws, we applied ensemble control to drive a swarm of motors to desired velocities using the uniform magnetic gradient of a clinical MRI scanner [78]. All this work has one serious drawback: the complexity of the control law increases quadratically with the number of robots, as shown in Figs. 1.4 and 1.8. Because swarms of robots can now number in the millions, progress requires techniques that scale sublinearly (or are constant) with population size. Section 1.4 discusses techniques that use collisions with obstacles to break the symmetry of the control input. These techniques can often exploit the environment to efficiently reconfigure the swarm. A concluding medical example: our work using an MRI to self-assemble Gauss gun components floating inside a spinal-fluid model relied on obstacles to break symmetry and achieve quasi-independent control of three components [7].
Many microrobots, including all those in Fig. 1.2, have kinematics that match the kinematic unicycle model. This model describes each robot with an location and heading θ, with two control inputs, namely, linear velocity and angular velocity . and are functions of time, but we assume that the same and are applied to every robot.
With this model, consider a collection of n unicycles that each roll without slipping. Following the terminology of [58,59,64], we call this collection an ensemble and describe the configuration of the ith robot by and its configuration space by . The global control inputs are the forward speed and turning rate . We assume that each robot has a nonzero parameter that scales the linear velocity and a unique nonzero parameter that scales the turning rate ( ). These values may arise from stochastic processes during manufacturing [16], or as design decisions [79]. The kinematics of the unicycle are given by
If is zero, the robot cannot move. Similarly, prevents the robot from turning. On a collection of differential-drive robots, these parameters can be mapped to unique wheel sizes and .
We model our robotic system with a discrete-time model. We can simplify (1.1) by splitting each ΔT time step into two stages with piecewise constant inputs. During the first stage of round k we command the robots to turn in place ϕ, and during the second stage command the linear movement .
A control law that steers each robot to their goal alternates between having all robots turn in place and then commanding all the robots to move forwards or backwards. During the first stage of round k we command the robots to turn in place ϕ, and during the second stage command the linear movement
This controller requires that either all robots turn at slightly different rates or that robots when commanded to turn have stochastic variations. Either condition is possible by naturally occurring [57] or designed parameter variations during robot construction [16]. As long as ϕ meets the constraints on the sampling frequency given by the Nyquist frequency, our globally asymptotically stable control results follow. The control policy (1.3) is easy to implement, never increases the summed distance of the ensemble from the goal, and is robust to standard models of noise.
Fig. 1.5 shows simulations of the first 100 commands to an ensemble of two robots. Below each drawing of the robots at a specified number of turns is a plot of the sum squared distance of each robot to their goal locations. This error function is always quadratic. At each step, the linear velocity control input is chosen that minimizes the error function. This results in a control law that is globally asymptotically stable. Fig. 1.6 shows the same procedure with six robots. The error function is always quadratic. The fact that the error function is quadratic for arbitrary goal locations and any number of robots was surprising to us, so we made an interactive online demonstration you can use to steer robots to goal locations [80]. Alternately, purchase multiple RC cars that all have the same control frequency and practice steering them to goals. This experiment costs less than $20, and is popular with all ages.
Global inputs dictate that every robot receives the same control commands. The previous section exploited the fact that all robots, especially at the microscale, experience stochastic disturbances and so react differently to inputs. This section instead exploits the fact that robots often move in an environment rich with obstacles. These obstacles exert position-dependent forces on the robots, and can therefore often be used to efficiently manipulate the swarm towards a desired configuration.
Model: At microscale, viscous forces dominate inertial forces [81], giving a simple kinematic model
Here the control input is globally applied to robots with positions for .
In nonprehensile manipulation, a robot affects its environment without grasping [82–84]. In some ways, our problem formulation is the inverse of nonprehensile manipulation. Rather than just use a robot to restructure the environment, we use the environment to restructure a population of robots.
We can also use a large population of robots for traditional nonprehensile tasks, such as transporting objects using the flow of the robots [85], and manipulating an object too heavy for a single robot. Our control formulation enables efficient control of this kind of transport.
We illustrate our points with a simplified BlockWorld abstraction. The workspace is a rectangular grid in which each square is marked either free, fixed, or robot. All robots are controlled by a shared input command from the set , and can move horizontally and vertically in the grid, as long as there are no fixed squares stopping the robot. The boundary of the grid is composed of fixed squares.
The general case of motion-planning in a world composed of even a single robot and both fixed and moveable squares is in the complexity class PSPACE-complete [86]. Adding an additional robot does not decrease this complexity: given any single-robot problem, we can place a second robot in the boundary of the world and surround it with fixed squares without changing the original problem's complexity. Still, there are many tractable subproblems.
This section presents an algorithm to control the position of n robots using a single obstacle. We employ the BlockWorld abstraction, where the robots and the obstacle are unit squares. Each call to Algorithm 1 moves one robot from its starting position to its goal position.
Notation The starting position of the kth robot in world coordinates is , its desired final position is , and its position at time t is . We define fixed-size, axis-aligned bounding boxes S and F such that and . The bottom left corners of S and F are and , and are of width and height . Because all robots are identical, without loss of generality the robot indices are arranged in raster-scan order left-to-right, top-to-bottom in S and top-to-bottom, left-to-right in F. We note that the position of the kth robot may be specified in local reference frame: . The unmoving obstacle is located at . We assume the obstacle position , the starting positions , and the final positions are disjoint. Without loss of generality, we will assume that S is to the lower right of the obstacle and F is to the upper left of the obstacle, as illustrated in Fig. 1.7.
Procedure At the beginning of the kth call, the time is t, the bounding boxes S and F have been returned to their initial positions on opposite corners of O, the first robots have been moved to their proper positions in F, the remaining robots are in their original columns in S, and O is between S and F. The kth robot starts in position and should be moved to .
The algorithm consists in “popping” the kth robot out of the bounding box (steps 1–3), pushing the kth robot to the correct x coordinate relative to (steps 4–7), pushing the kth robot to the correct y coordinate relative to (steps 8–10), and returning the S and F bounding boxes to their original positions on either side of O (steps 11–12).
The commanded distance to move the kth robot from to the final destination is bounded by:
The total distance commanded for position control of n robots is the sum:
Analysis Algorithm 1 always requires 12n control switches. The worst-case running time for Algorithm 1 occurs when S and F are sparse and/or have large aspect ratios, and the algorithm runs in time. For more reasonable arrays, when S and F are dense with aspect ratios near 1, the running time approaches .
Algorithm 1 requires at least free space to the left, to the right, above, and below the obstacle:
Simulation Simulation results are shown in Fig. 1.8 for five arrangements with an increasing number of robots. We compare the total distance moved and commanded with the LAP distance—the shortest distance according to the Linear Assignment Problem using Manhattan distance. Because all robots are interchangeable, the LAP distance reduces to
Manufacturing microrobots has a host of challenges, but there is significant progress by roboticists, biologists, and chemists, who are now producing large populations of simple robots [21,32,34]. Controlling large populations of robots with limited capabilities is difficult, due to communication and onboard-computation constraints. Rather than focus on a particular design, this chapter reviewed recent work on controlling large numbers of agents using a global input. Section 1.3 examined global controls given in the local reference frame of each robot, in the form of angular and velocity commands. Section 1.4 examined a class of controllers that applies controls in a global references frame.
For an in depth analysis of the complexity of motion planning problem with global inputs see [89–93]. For recent work on swarm manipulation and shape control of a swarm see Shahrokhi and Becker [94–96].
3.147.48.78