Control of swarming robots

Abstract

Systems and methods for controlling a swarm of mobile robots are disclosed. In one aspect, the robots cover a domain of interest. Each robot receives a density function indicative of at least one area of importance in the domain of interest, and calculates a velocity vector based on the density function and a displace vector relative to an adjacent robot. Each robot moves to the area of importance according to its velocity vector. In some aspects, the robots together perform a sequence of formations. Each robot mimics a trajectory as part of its performance by switching among a plurality of motion modes. Each robot determines its next motion mode based on a displacement vector relative to an adjacent robot.

Claims

1. A multi-robot system comprising: mobile robots; and a touchable screen that outputs a time-varying density function in response to a touch on the touchable screen and determines the time-varying density function based on a position and amount of the touch on the touchable screen; wherein the mobile robots are responsive to the time-varying density function indicative of an area of importance defined at the touchable screen in a dynamically changing domain of interest; wherein the mobile robots are configured to spread into the dynamically changing domain of interest; and wherein each robot includes: a sensor for detecting relative distance and angle measurements of an adjacent robot; and a processor, coupled to the sensor, the processor configured to: receive, from the sensor, data representative of the relative distance and angle measurements of the adjacent robot; determine a displacement vector relative to the adjacent robot based on the relative distance and angle measurements detected by the sensor; and calculate a velocity vector based on the time-varying density function.

2. The multi-robot system of claim 1, wherein each robot further comprises a memory storing data representative of the dynamically changing domain of interest; and wherein the processor is further configured to: receive data representative of the time-varying density function indicative of the area of importance in the dynamically changing domain of interest; calculate the velocity vector based on both the time-varying density function and the displacement vector relative to the adjacent robot; and output for moving the robot to the area of importance in the dynamically changing domain of interest based on the velocity vector.

3. The multi-robot system of claim 2, wherein the dynamically changing domain of interest is divided based on the Voronoi cell partition, and each robot occupies a Voronoi cell.

4. The multi-robot system of claim 3, wherein the processor is further configured to compute a change in the robot's Voronoi cell, and a change in the adjacent robot's Voronoi cell.

5. The multi-robot system of claim 4, wherein the processor is further configured to calculate the velocity vector to compensate for the changes.

6. The multi-robot system of claim 2, wherein the processor is further configured to receive the data representative of the time-varying density function from the touchable screen.

7. A method for controlling a multi-robot system comprising robots, wherein the robots are responsive to a time-varying density function indicative of an area of importance in a dynamically changing domain of interest, and wherein each robot includes a sensor and a processor, the method comprising: receiving, by the processor on each robot, from the sensor, data representative of the relative distance and angle measurements of the adjacent robot; determining, by the processor, a displacement vector relative to the adjacent robot based on the relative distance and angle measurements detected by the sensor; receiving data representative of the time-varying density function from a computing device having a touch screen; determining the time-varying density function based on a position and amount of a touch on the touch screen; calculating a velocity vector based on the time-varying density function and the displacement vector relative to the adjacent robot; and outputting for moving the robot to the area of importance in the dynamically changing domain of interest based on the velocity vector; wherein the robots are configured to spread into the dynamically changing domain of interest.

8. A multi-robot system comprising mobile robots; wherein the robots are responsive to a density function indicative of an area of importance in a dynamically changing domain of interest; wherein the robots together perform a sequence of formations in a decentralizing manner, each robot mimicking a trajectory as part of its performance, each robot mimicking the trajectory by switching among motion modes; and wherein each robot includes: a sensor for detecting relative distance and angle measurements of an adjacent robot; and a processor, coupled to the sensor, the processor configured to: receive, from the sensor, data representative of the relative distance and angle measurements of the adjacent robot; determine a displacement vector relative to the adjacent robot based on the relative distance and angle measurements detected by the sensor; receive data representative of the sequence of formations; determine a scaling factor for the robot's next mode based on the displacement vector; determine a rotation factor for the robot's next mode based on the displacement vector; determine a switch time for the robot's next mode based on the displacement vector; and output for executing the next mode based on the scaling factor, the rotation factor and the switch time.

9. The multi-robot system of claim 8, wherein the processor is further configured to optimize the scaling factor, rotation factor and switch time based on an optimality condition and a costate equation.

10. The multi-robot system of claim 8, wherein the processor is further configured to optimize the scaling factor, rotation factor and switch time by performing a steepest decent algorithm.

11. The multi-robot system of claim 8, wherein the scaling factor scales the displacement vector by multiplying a relative distance measurement between two adjacent robots by a constant.

12. The multi-robot system of claim 8, wherein the rotating factor rotates the displacement vector by adding a constant to a relative angle measurement.

13. A method for controlling the multi-robot system of claim 8 comprising: receiving, by the processor on each robot, the data representative of the sequence of formations in a decentralizing manner; receiving, by the processor, from the sensor, data representative of relative distance and angle measurements between the robot and its adjacent robot; determining, by the processor, the displacement vector relative to the adjacent robot based on the relative distance and angle measurements; determining the scaling factor for the robot's next mode based on the displacement vector; determining the rotation factor for the robot's next mode based on the displacement vector; determining the switch time for the robot's next mode based on the displacement vector; and outputting for executing the next mode based on the scaling factor, the rotation factor and the switch time; wherein the robots perform the sequence of formations in a decentralizing manner.

14. The method of claim 13 further comprising optimizing the scaling factor, rotation factor and switch time based on an optimality condition and a costate equation.

15. The method of claim 13 further comprising optimizing the scaling factor, rotation factor and switch time by performing a steepest decent algorithm.

16. The method of claim 13 further comprising scaling with the scaling factor the displacement vector by multiplying a relative distance measurement between two adjacent robots by a constant.

17. The method of claim 13 further comprising rotating with the rotating factor the displacement vector by adding a constant to a relative angle measurement.

18. The multi-robot system of claim 8, wherein the processor is further configured to receive data representative of the density function from an interface.

19. The multi-robot system of claim 8 further comprising an interface; wherein the mobile robots are configured to spread into the dynamically changing domain of interest; and wherein the interface comprises a touchable screen that outputs the density function in response to a touch on the touchable screen, and determines the density function based on a position and amount of the touch on the touchable screen.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The following Detailed Description technology is better understood when read in conjunction with the appended drawings. For the purposes of illustration, there is shown in the drawings exemplary embodiments, but the subject matter is not limited to the specific elements and instrumentalities disclosed.

(2) FIG. 1 provides a schematic illustration of a multi-robot network in accordance with one aspect of the disclosed technology.

(3) FIG. 2 provides an example illustration of interactions between an operator and a team of robots in accordance with one aspect of the disclosed technology.

(4) FIG. 3 provides a perspective view of a tablet with light shown in its touch panel in response to human touch in accordance with one aspect of the disclosed technology.

(5) FIGS. 4-5 illustrate examples of commanding the team of robots by manipulating light on the touch panel of the tablet in accordance with one aspect of the disclosed technology.

(6) FIG. 6 illustrates a perspective view of the tablet with multiple lights shown in its touch panel in response to multiple finger touches in accordance with one aspect of the disclosed technology.

(7) FIG. 7(a)-(f) illustrates movement of the team of robots in a domain of interest partitioned by the Voronoi cells in accordance with one aspect of the disclosed technology.

(8) FIG. 8 illustrates an instantaneous locational cost when executing TVD-D.sub.1 under a density function in accordance with one aspect of the disclosed technology.

(9) FIG. 9 illustrates the magnitude of .sub.max of as a function of time when executing TVD-D.sub.1 under a density function in accordance with one aspect of the disclosed technology.

(10) FIG. 10 is a flow diagram of a method, according to one aspect of the disclosed technology.

(11) FIG. 11 is a flow diagram of a method according another aspect of the disclosed technology.

(12) FIG. 12(a)-(l) illustrates simulation of optimally decentralized version of a drumline-inspired dance with multiple robots in accordance with one aspect of the disclosed technology.

(13) FIG. 13 illustrates a convergence of cost J after running steepest descent for 5000 iterations in accordance with one aspect of the disclosed technology.

(14) FIG. 14 illustrates a pictorial example of scripting language in accordance with one aspect of the disclosed technology.

(15) FIG. 15 illustrates an envisioned interface for the scripting language in accordance with one aspect of the disclosed technology.

(16) FIG. 16 illustrates a graphical user interface for controlling three robots in accordance with one aspect of the disclosed technology.

DETAILED DESCRIPTION

(17) To facilitate an understanding of the principles and features of the various embodiments of the present invention, various illustrative embodiments are explained below. Although exemplary embodiments of the present invention are explained in detail, it is to be understood that other embodiments are contemplated. Accordingly, it is not intended that the present invention is limited in its scope to the details of construction and arrangement of components set forth in the following description or examples. The present invention is capable of other embodiments and of being practiced or carried out in various ways. Also, in describing the exemplary embodiments, specific terminology will be resorted to for the sake of clarity.

(18) It must also be noted that, as used in the specification and the appended claims, the singular forms a, an and the include plural references unless the context clearly dictates otherwise. For example, reference to a component is intended also to include composition of a plurality of components. References to a composition containing a constituent is intended to include other constituents in addition to the one named.

(19) Also, in describing the exemplary embodiments, terminology will be resorted to for the sake of clarity. It is intended that each term contemplates its broadest meaning as understood by those skilled in the art and includes all technical equivalents that operate in a similar manner to accomplish a similar purpose.

(20) Ranges may be expressed herein as from about or approximately or substantially one particular value and/or to about or approximately or substantially another particular value. When such a range is expressed, other exemplary embodiments include from the one particular value and/or to the other particular value.

(21) Similarly, as used herein, substantially free of something, or substantially pure, and like characterizations, can include both being at least substantially free of something, or at least substantially pure, and being completely free of something, or completely pure.

(22) By comprising or containing or including is meant that at least the named compound, element, particle, or method step is present in the composition or article or method, but does not exclude the presence of other compounds, materials, particles, method steps, even if the other such compounds, material, particles, method steps have the same function as what is named.

(23) It is also to be understood that the mention of one or more method steps does not preclude the presence of additional method steps or intervening method steps between those steps expressly identified. Similarly, it is also to be understood that the mention of one or more components in a composition does not preclude the presence of additional components than those expressly identified. Such other components or steps not described herein can include, but are not limited to, for example, similar components or steps that are developed after development of the disclosed technology.

(24) The materials described as making up the various elements of the present invention are intended to be illustrative and not restrictive. Many suitable materials that would perform the same or a similar function as the materials described herein are intended to be embraced within the scope of the present invention. Such other materials not described herein can include, but are not limited to, for example, materials that are developed after the time of the development of the present invention.

1. Multi-Robot Network

(25) FIG. 1 illustrates a multi-robot network 100. The network 100 may include at least two robots 110 spatially distributed. Each robot 110 may also be known as an agent. The network 100 may include hundreds or thousands of robots 110. In the example as illustrated in FIG. 1, the network 100 may include robots 110a-e. Each robot may be a mobile robot, such as a wheeled ground robot. For instance, each robot may be a differential-drive robot, such as a Khepera III differential-derive mobile robot from K-team.

(26) Robots may collaborate with each other to collectively complete one or more tasks. Each robot may have different capabilities. The robots may negotiate among themselves to accomplish the tasks. The robots may assemble as a team, into the most efficient positions, relative to each other. Each robot may include pre-programmed algorithms in its controlling software which serves as the language that each robot uses to define and solve problems as a group.

(27) In one example, a Robot Operating System (ROS) framework running on an Ubuntu machine with a processor and memory may be used to implement the algorithm. The Ubuntu machine may be a smart phone, tablet or any computing device. The Ubuntu machine may have a version of 11.04. The processor may be an Intel dual core CPU 2.13 GHz. The memory may be 4 GB. The ROS may have a version of Diamondback. The ROS may send control signals to individual robots over a wireless router. Each robot may have a processor, embedded Linux, differential drive wheels, and a wireless card for communication over a wireless router. The processor on each robot may be 600 MHz ARM with 128 Mb RAM. The processors of the robots may have clocks that can be synchronized and remain synchronized for a period of time afterwards. The robots may communicate with one another wirelessly with built-in sensors. Using the pre-programmed algorithms in the software, the robots may know their roles and communicate with each other wirelessly.

(28) Each robot may not know the entire universe of the robots in the network 100. Each robot may not have a have Global Positioning System thereon, and thus may not have or know the global coordinates. However, each robot may have a sensor. The sensor may measure a relative displacement of adjacent robots in real-time. The sensor on a robot may detect adjacent robots within a close proximity (also known as neighbors). The robot may move to a center of its local neighborhood. The robot may determine its new position based on its local neighborhood. For example, the robot's new position may be calculated as a function of distance between adjacent robots. For instance, with reference to FIG. 1, if a robot 110a is too far from an adjacent robot 110b, then the robot 110a may move closer to the adjacent robot 110b. On the other hand, if the robot 110a is too close to the adjacent robot 110b or collide into the adjacent robot 110b, then the robot 110a may move away from the robot 110b.

(29) The sensing technology implemented by the robots may be LIDAR or vision-based sensing. For instance, each robot may include at least a motion capture camera to provide real-time position and orientation data for the robot. In some instances, each robot may include two motion capture cameras. The motion capture camera may be an Optitrack S250e motion capture camera.

(30) Based on the relative distance and angle between itself and each of its neighbors, each robot may perform simple operations on these vectors such as scaling and rotation. Scaling of the relative displacement vector may refer to multiplying the relative distance measurement by a constant. Rotating the relative displacement vector may be performed by adding a constant to the relative angle measurement. The scaled and rotated displacement vectors may also be added together using vector addition.

(31) The control of the robots in the network 100 may be decentralized in the sense that all notions of direction in the control signal may be derived from the pairs of relative distance and angle measurements made between a robot and its neighbors. Each robot's decentralized controller may be constrained to be parameterized functions of the relative distances and angles between the robot and its adjacent robots.

2. Human-Swarm Interaction

(32) FIG. 2 illustrates an example of interactions between an operator 120 and a swarm of robots 110. The operator 120 may interact with the robots at the team level, for instance, by giving the robots a high-level direction. The robots may negotiate among themselves and with the human operator. The robots may figure out how to accomplish the task. Each robot may be autonomous in the sense that each makes its own decision.

(33) In one example, the operator 120 may instruct the team of robots to cover an area of importance in a domain of interest. The domain of interest may include many areas of importance. The operator 120 may control the team of robots via a smart phone, a tablet, a joystick or any computing device. In the example of FIG. 2, the operator 120 may place or swipe one or more fingers on a tablet 130. The touch screen of the tablet 130 may correspond to the domain of interest. As the operator 120 places or moves a finger on the touch screen, the touched area on the touch screen may light up as illustrated in FIG. 3. The light 140 may diminish in a gradient fashion from the touched area, such that the touched area may have a higher brightness than untouched areas. The finger's position on the touch screen may dictate the area of importance for the team of robots to move to. The brighter the light is, the more important the area is. As such, the finger's position may provide a rough reference for where the team of robots should be located.

(34) By moving the finger, the operator 120 may change the light density of different areas on the touch screen. As illustrated in FIGS. 3-5, by manipulating the light density, the operator 120 may manipulate the general moving direction of the team of robots as a whole. The tablet 130 may provide the external, human-generated density function to the network of robots as an input. Density functions may represent rough references for where the robots should be located.

(35) The tablet 130 may send the light density to each robot. Each robot may move into the area of importance as indicated by the light density. For example, whenever a touch occurs on the tablet 130 screen, the processor in the tablet 130 may identify the position of the touch, and its corresponding area in the domain of interest. The corresponding area in the domain of interest may be regarded as the area of importance. The tablet 130 may send the densities values of the touched area to each robot. As shown in FIG. 6, multiple touches 140a and 140b may occur at the same time. The tablet 130 may send corresponding density values of each touched area to the robots. As the light density changes, the robots may move accordingly towards the area of importance as represented by the light. The density function may be independent of the team size of the robots.

(36) In one example, the operator 120 may externally influence the team of robots via a time-varying density function. The continuous-time algorithm may move the robots so as to provide optimal coverage given the density functions as they evolve over time. In this example, each robot in the team of robots may be implemented with a coverage algorithm based on time-varying density functions.

(37) Each robot may store in its local memory a boundary of the domain of interest. In one example, each robot may not have any map beyond where the domain is located.

(38) Mathematically speaking, D .sup.2 may be the two-dimensional convex domain representing the domain of interest. : D[0, ).fwdarw.(0, ) may be the associated density function, which may be bounded and continuously differentiable in both arguments, where (q,t) may capture the relative importance of a point q D at time t. Below are two examples of Density function :

(39) $\begin{array}{cc}{}_1\left(q,t\right)=e^{-\left({\left(q_x-2\sin \left(\frac{t}{}\right)\right)}^2+{\left(\frac{q_y}{4}\right)}^2\right)}& \left(1\right)\\ {}_2\left(q,t\right)=\underset{=1}{\overset{M}{.Math.}}{e}^{-\left({\left(q_x-{}_{x,}\left(t\right)\right)}^2+{\left(q_y-{}_{y,}\left(t\right)\right)}^2\right)}& \left(2\right)\end{array}$
For example the time constant may be =5. For example (.sub.x,l(t), .sub.y,l(t)) may represent the position on D of the l.sup.th touch out of M touches on the tablet at time t.

(40) Each robot may be differential-drive robot, and may be modeled as unicycles,
{dot over (x)}.sub.i=.sub.i cos .sub.i (3)
{dot over (y)}.sub.i=.sub.i sin .sub.i (4)
{dot over ()}.sub.i=.sub.i (5)
where (x.sub.i, y.sub.1) may represent the position of robot i, .sub.i may represent the heading of the robot i, and .sub.i, .sub.i may represent the translational and angular velocities of the robot i. The position of the ith robot may be represented as p.sub.i D, i=1, . . . , n. The desired motions for each robot i may also be represented in terms of {dot over (p)}.sub.i for purposes of the coverage algorithm, where {dot over (p)}.sub.i may be mapped onto .sub.i, .sub.i through the following equations:

(41) $\begin{array}{cc}{v}_i=.Math.{\stackrel{.}{p}}_i.Math.& \left(6\right)\\ {}_i=\left[\begin{array}{cc}-\sin {}_i& \cos {}_i\end{array}\right].Math.\frac{{\stackrel{.}{p}}_i}{.Math.{\stackrel{.}{p}}_i.Math.}.& \left(7\right)\end{array}$

(42) An optimal partition of the domain of interest may be represented as follows to ensure optimal coverage of the domain by the robots with minimal locational cost:
V.sub.i(p)={q D|qp.sub.iqp.sub.j, ij}(8)
This partition of D may be regarded as a Voronoi tessellation. V.sub.i may denote the region. The Voronoi partitions may be computed based on the position and orientation data provided by motion capture cameras on the robots.

(43) Since 0, the mass m.sub.i and center of mass c.sub.i of the i-th Voronoi cell, V.sub.i, may be defined as

(44) $\begin{array}{cc}{m}_i\left(p,t\right)={}_{V_i\left(p\right)}^{}\left(q,t\right)dq& \left(9\right)\\ c_i\left(p,t\right)=\frac{{}_{V_i\left(p\right)}^{}q\left(q,t\right)dq}{m_i}& \left(10\right)\end{array}$
p may be a so-called Central Voronoi Tesselation (CVT).

(45) The CVT may refer to a configuration where the positions of each robot coincide with the centroids of their Voronoi cells, given a so-called Voronoi tessellation of the domain of interest. When at a CVT, the robots may reach a configuration, mathematically represented as {p.sub.ic.sub.i.sup.2=0, i=1, . . . , n}, i.e., to a CVT. The Voronoi cell partition may be independent of the density. FIG. 7(a)-(f) illustrates a team of five mobile robots implemented with distributed coverage algorithm. In FIG. 7(a)-(f), the thick lines represent delineation of the Voronoi cells 150a-e, whose centers of mass 160a-e are shown as dark circles. Each Voronoi cell may represent a portion of space closest to a robot. For example, each of the Voronoi cells 150a-e may respectively represent a portion of space closest to one of the robots 110a-e. As shown in FIG. 7(a-(f), the Voronoi cells partition may constantly change as robots 110a-e move. The robots 110a-e may calculate their Voronoi cells based on the positions of their neighbors. Based on the density information it receives, each robot may predict how its Voronoi cell will change, and how its neighbors' cells will change, as it moves to better cover the density, and compensates for this change in its motion.

(46) To achieve optimal coverage, the robots may initially converge to the CVT associated with a static density function. For example, at an initialization step, the CVT may be achieved at initial time t.sub.0, i.e., p (t.sub.0)=c(p(t.sub.0), t.sub.0)), where c=[c.sub.1.sup.T, . . . , c.sub.n.sup.T].sup.T. A static density function may be chosen initially. Until the robots achieve a CVT, and a time-invariant algorithm, such as Lloyd's algorithm as shown below, may be deployed. This may happen asymptotically.
{dot over (p)}.sub.i=k(p.sub.ic.sub.i) (11)
{dot over (p)}.sub.i may represent a gradient descent motion for each individual robot to execute, where k may be a positive gain. (p.sub.i c.sub.i) may represent the gradient direction (with respect to p.sub.i).

2.1 Time-Varying Density Function

(47) After the robots reach the CVT, the initialization process may end. Following the initialization, the robots may maintain the CVT by executing a time-varying density function implemented on each robot. Timing information must be included in the motion of the robots. The robots may not need to share a sense of direction in a global frame. Each robot may determine its own motion based on information of adjacent robots.

(48) For instance, each robot may determine its velocity vector based on relative displacement vectors with respect to its neighbors. The velocity vector may be computed by a time-varying density function. Mathematically speaking, the update rule for {dot over (p)}.sub.i may only depend on p.sub.j, j N.sub.i, as well as p.sub.i itself. N.sub.i may represent the set of Voronoi cells adjacent to Voronoi cell i. Two Voronoi cells may be adjacent if they share a face.

(49) Each robot may determine its velocity vector to best cover the density. Each robot may determine its velocity vector in a manner to compensate for the density changing over time, and to compensate for its neighbors' movement.

(50) The time-varying density function may be derived using well-posed Neumann approximation of the inverse as a mechanism for achieving the distributed version of a time-varying centralized function.

2.1.1 TVD-D1

(51) Below is an example time-varying-density, decentralized with 1-hop adjacency information (TVD-D.sub.1). The gradient descent motion {dot over (p)}.sub.i for each individual robot to execute may be calculated as follow:

(52) $\begin{array}{cc}{\stackrel{.}{p}}_i=\frac{c_i}{t}-k\left(p_i-c_i\right)+\underset{j{N}_{V_j}}{.Math.}\frac{c_i}{p_j}\left(\frac{c_j}{t}-k\left(p_j-c_j\right)\right).& \left(12\right)\end{array}$
where (p.sub.ic.sub.i) may represent the gradient direction (with respect to p.sub.i).

2.1.2 Computation of Term

(53) $\frac{c}{p}$

(54) Leibniz rule must be exercised to compute the term

(55) $\frac{c}{p}.$
In the following, p.sub.j.sup.(b) may denote the b-th component of the vector p.sub.j. When D .sup.2, b=1,2 represents a planar case. Based on Leibniz rule, the following equations may be obtained:

(56) $\begin{array}{cc}\frac{c_i^{\left(a\right)}}{p_j^{\left(b\right)}}=\left({}_{V_{i,j}}^{}{q}^{\left(a\right)}\frac{p_j^{\left(b\right)}-q^{\left(b\right)}}{.Math.p_j-p_i.Math.}dq\right)/m_i-\left({}_{V_{i,j}}^{}\frac{p_j^{\left(b\right)}-q^{\left(b\right)}}{.Math.p_j-p_i.Math.}dq\right)\left({}_{V_i\left(P\right)}^{}{q}^{\left(a\right)}dq\right)/m_i^2& \left(13\right)\end{array}$
where =1,2 and where ij.

(57) Similarly, when i=j, the following equation may be obtained:

(58) $\begin{array}{cc}\frac{c_i^{\left(a\right)}}{p_i^{\left(b\right)}}=-\underset{k{N}_{V_i}}{.Math.}\left[\left({}_{V_{i,k}}^{}{q}^{\left(a\right)}\frac{q^{\left(b\right)}-p_i^{\left(b\right)}}{.Math.p_k-p_i.Math.}dq\right)/m_i-\left({}_{V_{i,k}}^{}\frac{q^{\left(b\right)}-p_i^{\left(b\right)}}{.Math.p_k-p_i.Math.}dq\right)\left({}_{V_i\left(P\right)}^{}{q}^{\left(a\right)}dq\right)/m_i^2\right]& \left(14\right)\end{array}$

2.1.3 Locational Cost

(59) FIG. 8 illustrates an instantaneous locational cost when executing TVD-D.sub.1 under density function .sub.2. The locational cost may represent the minimum distance that each robot has to drive. The locational cost may describe how well a given area is being covered. The locational cost may evaluate how effective given robot configurations are at achieving coverage. The locational cost may be computed as follows:

(60) $\begin{array}{cc}H\left(p,P,t\right)=\underset{i=1}{\overset{n}{.Math.}}{}_{P_i}^{}{.Math.q-p_i.Math.}^2\left(q,t\right)dq& \left(15\right)\end{array}$
As shown in FIG. 8, even when the magnitude of the maximal eigenvalue hovers close to 1 for longer periods of time, the Neumann approximation TVD-D.sub.1 remains valid, and does not affect the performance of the algorithm. FIG. 9 illustrates the magnitude A.sub.max of as a function of time when executing TVD-D.sub.1 under density function .sub.2, where .sub.max may denote the eigenvalue with the largest magnitude of the matrix

(61) 0$\frac{c}{p}.$

2.1.4. TVD-Dk

(62) When higher order terms are kept in the Neumann series, dist(i, j) may denote the distance between cells i and j. In one example, dist(i, j) may represent an edge distance between i and j in the Delaunay graph induced by the Voronoi tesselation.

(63) $\frac{c}{p}$
may represent a (block) adjacency matrix, the following may be obtained:

(64) $\begin{array}{cc}{\left[{\left(\frac{c}{p}\right)}^k\right]}_{\mathrm{ij}}0.Math.\mathrm{dist}\left(i,j\right)k,k=0,1,2,\mathrm{.Math.}& \left(16\right)\end{array}$
where [.Math.].sub.ij may denote the block corresponding to cell c.sub.i and robot position p.sub.j.

(65) The k-hop version of TVD-D.sub.1 may be represented by TVD-D.sub.k, {dot over (p)} may be calculated as follows:

(66) $\begin{array}{cc}\stackrel{.}{p}=\underset{=0}{\overset{k}{.Math.}}{\left(\frac{c}{p}\right)}^{}\left(-k\left(p-c\right)+\frac{c}{t}\right),& \left(17\right)\end{array}$

2.2 Example Flow Diagram

(67) According to one aspect of the disclosed technology, a plurality of mobile robots may together cover a domain of interest. Each robot may include a processor. FIG. 10 is a flow-diagram of an example method, in accordance with an exemplary embodiment of the disclosed technology. In block 202, the processor may receive, from a sensor, data representative of the relative distance and angle measurements of an adjacent robot. In block 204, the processor may determine a displacement vector relative to the adjacent robot based on the relative distance and angle measurements detected by the sensor. In block 206, the processor may receive data representative of a density function indicative of at least one area of importance in the domain of interest. In block 208, the processor may calculate a velocity vector based on the density function and the displacement vector relative to the adjacent robot. In block 210, the processor may output for moving the robot to the at least one area of importance in the domain of interest based on the velocity vector.

(68) In one implementation, the processor of each robot may calculate the velocity vector based on displacement vectors relative to all adjacent robots.

(69) In one implementation, the processor may compute the velocity vector based on a time-varying density function.

(70) In one implementation, the domain of interest may be divided based on the Voronoi cell partition. Each robot may occupy a Voronoi cell. The processor may compute a change in the robot's Voronoi cell, and a change in the adjacent robot's Voronoi cell. The processor may calculate the velocity vector to compensate for the changes.

(71) In one implementation, the processor may receive the data representative of the density function from a computing device. The computing device may have a touchable screen. The computing device may output the density function in response to a touch on the screen, and may determine the density function based on a position and amount of the touch on the screen.

3. Scripted Formation

(72) According to another aspect of the present technology, a team of robots may be assigned to perform a sequence of motions or a sequence of formations, where the sequence of motions may be expressed in terms of trajectories of individual robots. Although the team as a whole is assigned to the task or mission, each robot may not have a pre-assigned role. Rather, once the team of the robots as whole is assigned to the task, individual robots may coordinate their own activities to perform or build the sequence.

(73) The team of robots may start in a random configuration. Once the team of robots is instructed to perform a sequence of motions or formations, the team of robots may perform the formation at any position and with any rotation. Each robot may know only the relative positions of the other robots. Each robot may independently identify the proper formation position as well as its role in the formation.

(74) Any formation may be disturbed when a new robot is added to the team, an exhibiting robot is removed from the team, or when an exhibiting robot is removed from its pose by an external factor such as an operator. When such a disturbance occurs, the team of robots may react by altering the assignment and formation pose.

(75) The information flow between robots may be given by a predetermined static graph topology. The information flow among the team of robots may be limited by a predefined network topology. Each robot may distinguish the identity of its neighbors from one another. The robots may have synchronized clocks allowing them to perform open-loop clock-based transitions between different controllers.

(76) For a given desired trajectory, the team of robots may optimally mimic the trajectory using a decentralized control law in the form of a switched autonomous system. In the switched autonomous system, each robot may have a plurality of modes that are parameterized by scaling and rotation factors associated with each neighbor. For instance, each robot may receive a formation shape. Based on relative displacement information, each robot may determine how to realize the shape. For example, each robot may determine where it should be located and rotated, and how it should be scaled.

(77) To perform a sequence of formations, each robot may switch between consecutive modes. Each robot may constantly reassess the best formation pose and role assignment. Each mode may be defined by a plurality of parameters. The parameters may include orientation, translation, and scaling of the formation. A robot may choose parameters that minimize the distance it has to drive. The optimal parameters may be the parameters that make the decentralized trajectories track the desired trajectories the best. To mimic the desired trajectory, the mode parameters and switch times may be optimized in a decentralized setting. To do this, certain pertinent results, such as optimality conditions and costate equations, may be derived for optimizing parameterized modes in a general setting, and then may be extended towards a decentralized setting. Similar results may be derived for switching times.

(78) For implementation, given a desired trajectory, the parameters and switch times may be optimized using a steepest decent algorithm on the above mentioned derived results. Each robot may then execute its motion dictated by these optimized parameters and switch times.

(79) The optimality conditions for the parameters may be derived as described herein.

3.1 System Dynamics

(80) In one embodiment, the team of robots may accomplish a mission, e.g., a desired sequence of motions or formations. Each robot's trajectory may start at time t=0, and end at time t=T. Each robot may switch modes for a total of K global switch times .sub.1, . . . , .sub.K, where
0=.sub.0.sub.1 . . . .sub.K.sub.K+.sub.1=T, (18)
with the kth mode occurring at the time interval [.sub.k1, .sub.k).

(81) Under global clock-based switching, each robot may have K+1 modes and each of its modes may be parameterized by scaling and rotation factors associated with each neighbor. The dynamics for the ith robot operating in the kth mode may be represented as follows:

(82) $\begin{array}{cc}{\stackrel{.}{x}}_{\mathrm{.Math.}}=-\underset{j{N}_i}{.Math.}{r}_{\mathrm{ijk}}\mathrm{Rot}\left({}_{\mathrm{ijk}}\right)\left(x_i-x_j\right)& \left(19\right)\end{array}$
with r.sub.ijk, and .sub.ijk [0, 2] being the constants used for scaling and rotating the displacement vector respectively between itself and robot j. The matrix

(83) $\begin{array}{cc}\mathrm{Rot}\left(\right)=\left[\begin{array}{cc}\cos \left(\right)& -\sin \left(\right)\\ \sin \left(\right)& \cos \left(\right)\end{array}\right]& \left(20\right)\end{array}$
may define the two-dimensional rotation matrix for counter-clockwise rotation of a vector.

(84) In the alternative, the dynamics in Equation (19) may be rewritten as follows:

(85) $\begin{array}{cc}{\stackrel{.}{x}}_{\mathrm{.Math.}}=-\underset{j{N}_i}{.Math.}{M}_{\mathrm{ijk}}\left(x_i-x_j\right)\mathrm{where}{M}_{\mathrm{ijk}}=\left[\begin{array}{cc}{a}_{\mathrm{ijk}}& -b_{\mathrm{ijk}}\\ b_{\mathrm{ijk}}& a_{\mathrm{ijk}}\end{array}\right],a_{\mathrm{ijk}}=r_{\mathrm{ijk}}\cos \left({}_{\mathrm{ijk}}\right),\mathrm{and}{b}_{\mathrm{ijk}}=r_{\mathrm{ijk}}\sin \left({}_{\mathrm{ijk}}\right).& \left(21\right)\end{array}$

(86) The entire system dynamics may be collected together in matrix form. Let x .sup.2N be

(87) $\begin{array}{cc}x=\left[\begin{array}{c}{x}_1\\ \mathrm{.Math.}\\ x_N\end{array}\right]& \left(22\right)\end{array}$
i.e., x contains the positions of the N robots. The (2N2N) adjacency matrix A.sub.k associated with the kth mode may be defined in terms of (22) blocks by

(88) $\begin{array}{cc}{A}_{\mathrm{ijk}}=\{\begin{array}{cc}{M}_{ijk}& \mathrm{if}\left(v_j,v_i\right)E\\ 0& \mathrm{otherwise}\end{array}.& \left(23\right)\end{array}$

(89) The (2N2N) degree matrix D.sub.k associated with the kth mode may be also defined in terms of (22) blocks, and may be given by

(90) $\begin{array}{cc}{D}_{\mathrm{ijk}}=\{\begin{array}{cc}\underset{z.Math.\left(v_z,v_i\right)E}{.Math.}{M}_{\mathrm{izk}}& \mathrm{if}i=j\\ 0& \mathrm{otherwise}\end{array}& \left(24\right)\end{array}$

(91) The weighted Laplacian L.sub.k associated with the kth mode may be defined as
L.sub.k=D.sub.kA.sub.k (25)

(92) The evolution of the switched autonomous system of N robots with K+1 modes may be described by the dynamics
{dot over (x)}=L.sub.kx t [.sub.k1, .sub.K), (26)
with mode indices k=1, . . . , K+1.

3.2 Optimal Decentralization

(93) For a system of N robots with positions x(t) and initial positions x(0)=x.sub.0, a decentralized version of a desired trajectory may be represented by x.sub.d(t). Given a desired trajectory for the multi-robot system, an aspect of the present technology may imitate that behavior using only decentralized control laws, while minimizing the cost functional
J=.sub.0.sup.Tx(t)x.sub.d(t).sup.2 dt (27)
for the team of robots with dynamics (26) by optimizing the parameters a.sub.ijk and b.sub.ijk for each of the K+1 modes, and the K global switch times .sub.k, while satisfying (1).

(94) The costate dynamics and optimality conditions for optimizing parameterized modes may be derived in a general setting. The results may be specialized to the decentralized system (26). The resulting optimality conditions and costate equations may be used in conjunction with a steepest descent algorithm. Together they may optimize the modes and global switching times of the decentralized system to minimize J, and thus optimally decentralize x.sub.d(t).

3.2.1 Parameterized Mode Optimization

(95) A switched autonomous system of robots may start at time t=0, and end at time t=T, with K+1 modes and K switching times. Each of the modes' dynamics may be given by the function f, but may be parameterized by different scalar parameters c.sub.k for each mode k. The switching times may be .sub.1, . . . , .sub.K satisfying (18), with the k th mode occurring in the time interval [.sub.k1, .sub.K). The dynamics of the system may be expressed as:
{dot over (x)}=F(x, C, t) (28)
with
F(x, C, t)=f(x, c.sub.k)t [.sub.k1, .sub.k), (29)
where c.sub.k may be free to be chosen and C=[c.sub.1, c.sub.k+1].sup.T. The objective is to choose C so as to minimize the generalized cost functional
J=.sub.0.sup.TH(x(t))dt (30)

(96) The optimality condition for each c.sub.k in (29) with respect to cost (30) may be represented as

(97) 0$\begin{array}{cc}{J}_{c_k}={}_{{}_{k-1}}^{{}_k}\frac{f}{c_k}{\left(,c_k\right)}^{T}p\left(\right)d=0& \left(31\right)\end{array}$
where p may represent the costate with dynamics

(98) $\begin{array}{cc}\stackrel{.}{p}=-{\left(\frac{F}{x}\right)}^{T}p-{\left(\frac{H}{x}\right)}^T& \left(32\right)\end{array}$
and boundary condition
p(T)=0 (33)

(99) To apply these results to the problem of optimal decentralization, the optimality conditions and costate dynamics may be specialized for the decentralized system (26) and cost (27). To minimize J, the parameters a.sub.ijk and b.sub.ijk associated with each of the K+1 modes may be optimized. Define a.sub.k=[ . . . a.sub.ijk, . . . ].sup.T and b.sub.k=[ . . . b.sub.ijk, . . . ].sup.T over all valid combinations of i and j allowed by the graph topology. They may represent vectors containing all the parameters appearing in the system dynamics for a particular mode k.

(100) Optimality conditions for a.sub.k and b.sub.k with respect to cost (27) may be computed as follows

(101) $\begin{array}{cc}{J}_{\mathrm{ak}}={}_{{}_{k-1}}^{{}_k}\frac{f}{a_k}{\left(,a_k\right)}^{T}p\left(\right)d=0.& \left(34\right)\\ J_{\mathrm{bk}}={}_{{}_{k-1}}^{{}_k}\frac{f}{b_k}{\left(,b_k\right)}^{T}p\left(\right)d=0.& \left(35\right)\end{array}$

(102) The

(103) $\frac{f}{a_k}$$\mathrm{and}$$\frac{f}{b_k}$
matrices may be populated using (21) blocks based on the following

(104) $\begin{array}{cc}\frac{f_i}{a_{\mathrm{ijk}}}=-\left(x_i-x_j\right)& \left(36\right)\\ \frac{f_i}{b_{\mathrm{ijk}}}=-\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]\left(x_i-x_j\right),& \left(37\right)\end{array}$
where f.sub.i may be the (21) block of f corresponding to the dynamics of agent i.

(105) The decentralized system dynamics (26) and cost functional (27) may also need to be substituted into the costate dynamics (32).

(106) Costate dynamics for calculating the optimality conditions of a.sub.k and b.sub.k in (34) and (35) may be represented as:
{dot over (p)}(t)=L.sup.T.sub.k p(t)x(t)+x.sub.d(t)t [.sub.k1, .sub.k), (38)

3.2.2 Switch Time Optimization

(107) The optimality condition with respect to cost functional (30) for switching times in a switched autonomous system where mode k has dynamics f parameterized by c.sub.k may be represented as:

(108) $\begin{array}{cc}\frac{J}{{}_k}={p\left({}_k\right)}^T\left(f\left(x\left({}_k\right),c_k\right)-f\left(x\left({}_k\right),c_{k+1}\right)\right)=0.& \left(39\right)\end{array}$

(109) The costate dynamics may be the same as (32) and boundary conditions (33). The switch time optimality conditions specialized for the system (26) with cost (27) may be given by

(110) $\begin{array}{cc}\frac{J}{{}_k}={p\left({}_k\right)}^T\left(L_{k+1}-L_k\right)x\left({}_k\right).& \left(40\right)\end{array}$
with costate dynamics the same as (38).

3.3 Example Flow Diagram

(111) According to one aspect of the disclosed technology, a plurality of mobile robots may together perform a sequence of formations. Each robot may mimic a trajectory as part of its performance. Each robot may mimic the trajectory by switching among a plurality of motion modes. Each robot may include a sensor and a processor. FIG. 11 is a flow-diagram of an example method, in accordance with an exemplary embodiment of the disclosed technology. In block 302, the processor may receive data representative of the sequence of formations, In block 304, the processor may receive, from the sensor, data representative of the relative distance and angle measurements of an adjacent robot. In block 306, the processor may determine a displacement vector relative to the adjacent robot based on the relative distance and angle measurements detected by the sensor. In block 308, the processor may determine a scaling factor for the robot's next mode based on the displacement vector. In block 310, the processor may determine a rotation factor for the robot's next mode based on the displacement vector. In block 312, the processor may determine a switch time for the robot's next mode based on the displacement. In block 314, the processor may output for executing the next mode based on the scaling factor, the rotation factor and the switch time.

(112) In one implementation, the processor of each robot may calculate displacement vectors relative to all its adjacent robots. The processor may determine parameters for the robot's next mode, including the scaling factor, rotation factor and switch time, based on the displacement vectors relative to all its adjacent robots.

(113) In one example implementation, the processor may optimize the scaling factor, rotation factor and switch time based on an optimality condition and a costate equation.

(114) In one example implementation, the processor may optimize the scaling factor, rotation factor and switch time by performing a steepest decent algorithm.

(115) In one example implementation, the scaling factor may scale the displacement vector by multiplying a relative distance measurement between two adjacent robots by a constant.

(116) In one example implementation, the rotating factor may rotate the displacement vector by adding a constant to a relative angle measurement.

3.4 Example Simulation

(117) FIG. 12(a-(l) showcases a simulation of the above optimal decentralization algorithm that involves tracking a complex drumline-inspired multi-robot trajectory. Drum line formations are traditionally designed by choreographers to be executed in a centralized manner. The position and path taken by band members at each moment in time have been predetermined to a high level of detail. As a result, band members spend a lot of time practicing to follow these predetermined paths. However, such an approach requires each band member to memorize paths taken throughout the entire dance sequence and have global sensing capabilities to know if they're in the correct position. Optimal decentralization described herein may mimic the original routine with high fidelity using decentralized control laws.

(118) In the example as illustrated in FIG. 12(a-(l), the optimal decentralization algorithm may be used on a drum line-inspired trajectory involving N=21 robots with arbitrarily chosen initial values for each of their parameterized modes. A total of K=22 global switching times may be inserted initially evenly spaced between the starting time t=0 and ending time t=T=10.78. The system of the robots may have up to 23 modes.

(119) FIG. 12(a-(l) illustrates the optimally decentralized trajectories resulting from the optimization, where the actual locations of the agents are marked by O's with lines connecting them to their desired location marked by X's. As seen in the simulation results, the resulting decentralized control laws may successfully mimic the original trajectory.

(120) A variant of the standard steepest descent with Armijo step size algorithm may be used to stochastically take turns optimizing the parameterized modes with high probability and switch times with low probability to drive the cost J to a local minimum. FIG. 13 illustrates the convergence of the cost J after a run of 5000 iterations.

3.5 Other Embodiments

(121) FIG. 14 illustrates a pictorial example of scripting language in accordance with one aspect of the disclosed technology. FIG. 15 illustrates an envisioned interface for the scripting language in accordance with one aspect of the disclosed technology.

(122) FIG. 16 illustrates a graphical user interface for controlling three robots in accordance with one aspect of the disclosed technology.

4. Advantages

(123) The multi-robot systems and its methods described herein may outperform the previously known systems and methods. In one aspect, the general time-varying density functions may allow multi-robot optimal coverage, and may allow convergence to local minima. This algorithm is well-posed, and may allow for distributed implementation, and thus may perform better than previously known algorithms

(124) The present technology may be adapted to many applications, including but not limited to search and rescue, surveillance, exploration of frontier, agriculture, disaster field, manufacturing plants, defense and national security to detect and clear threats, and any other military operations. For example, optimal coverage of density functions may be applied to multi-robot search and rescue scenarios, where the density function may represent the probability of a lost person being at a certain point in an area. Additionally, optimal coverage of density functions may be applied to multi-robot surveillance and exploration, where the density function may be modeled to be a function of the explored frontier.

(125) By way of another example, optimal coverage of destiny functions may be applied to multi-robot farming Teams of smaller, more agile robots may work in swarms to perform a host of framing functions, without the downside of large tractors that compact the soil and devour gas. Swarm robots may tend crops on a micro level, inspecting individual plants for moisture and insects, and make decisions based on what they find, such as watering or administering pesticides. Farmers may control and communicate with the robots using nothing more than iPad app. Robots may operate autonomously and continuously over a full crop-growing cycle.

(126) Numerous characteristics and advantages have been set forth in the foregoing description, together with details of structure and function. While the invention has been disclosed in several forms, it will be apparent to those skilled in the art that many modifications, additions, and deletions, especially in matters of shape, size, and arrangement of parts, can be made therein without departing from the spirit and scope of the invention and its equivalents as set forth in the following claims. Therefore, other modifications or embodiments as may be suggested by the teachings herein are particularly reserved as they fall within the breadth and scope of the claims here appended. The term exemplary used herein does not mean best mode, but rather, example.

(127) Accordingly, those skilled in the art will appreciate that the conception upon which the application and claims are based may be readily utilized as a basis for the design of other structures, methods, and systems for carrying out the several purposes of the embodiments and claims disclosed in this application. It is important, therefore, that the claims be regarded as including such equivalent constructions.

(128) Furthermore, the purpose of the foregoing Abstract is to enable the public generally, and especially including the practitioners in the art who are not familiar with patent and legal terms or phraseology, to determine quickly from a cursory inspection the nature and essence of the technical disclosure of the application. The Abstract is neither intended to define the claims of the application, nor is it intended to be limiting to the scope of the claims in any way.