InTechOpen uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Robotics » "Recent Advances in Robotic Systems", book edited by Guanghui Wang, ISBN 978-953-51-2571-6, Print ISBN 978-953-51-2570-9, Published: September 28, 2016 under CC BY 3.0 license. © The Author(s).

Chapter 7

Time-Energy Optimal Cluster Space Motion Planning for Mobile Robot Formations

By Kyle Stanhouse, Chris Kitts and Ignacio Mas
DOI: 10.5772/64615

Article top


State space variables for a three-robot cluster.
Figure 1. State space variables for a three-robot cluster.
Cluster parameterized phase plane for multiple .
Figure 2. Cluster parameterized phase plane for multiple .
Velocity along the cluster parameterized path for multiple .
Figure 3. Velocity along the cluster parameterized path for multiple .
Snapshots of cluster rotate and translate maneuver in 5-s intervals.
Figure 4. Snapshots of cluster rotate and translate maneuver in 5-s intervals.
Individual robot velocity profiles.
Figure 5. Individual robot velocity profiles.
Cluster parameterized phase plane for multiple .
Figure 6. Cluster parameterized phase plane for multiple .
Velocity along the cluster parameterized path for multiple .
Figure 7. Velocity along the cluster parameterized path for multiple .
Snapshots of cluster rotate and resize maneuver in 5-s intervals.
Figure 8. Snapshots of cluster rotate and resize maneuver in 5-s intervals.
Energy vs. trajectory duration.
Figure 9. Energy vs. trajectory duration.

Time-Energy Optimal Cluster Space Motion Planning for Mobile Robot Formations

Kyle Stanhouse1, Chris Kitts1, 4 and Ignacio Mas2, 3, 4
Show details


The motions of a formation of mobile robots along predetermined paths are optimized according to a tunable time-energy cost function using the cluster space approach to multiagent system specification and control. Upon path-parameterizing cluster state variables describing the geometry and pose of a multirobot group, an optimal control problem is formulated that incorporates formation dynamics and state constraints. The optimal trajectory is derived numerically via a gradient search, iterating over the initial value of one costate. A multirobot formation control simulation is then used to demonstrate the effectiveness of the technique. Results indicate that a substantial tradeoff is made between energy expenditure and motion time when considered as minimization criteria in varying proportions, allowing the operator to tailor mission trajectories according to desired levels of each.

Keywords: time-energy optimization, motion planning, multirobot systems, cluster control

1. Introduction

In recent years, multiagent robotic systems have been firmly established as an important topic of research owing to the continued emergence of potential applications. Cooperating teams of robots remotely operated or capable of autonomous navigation and sensing can be used to enhance or extend the functions of single-agent systems in areas such as airborne [13] and terrestrial-distributed mobile sensing [46], search and rescue [79], and intelligent transportation [1012].

For mobile systems, one of the key technical considerations is the development of a technique to coordinate the motions of individual vehicles. The mutual goal of each agent is typically to establish and maintain a certain spatial configuration or to perform complicated geometrically time-varying maneuvers, a use case of particular interest to this investigation. These desired behaviors lead to a variety of formation control problems, for which a wide range of solutions have been and continue to be explored.

Notable work in this area includes the development of leader-follower strategies in which follower agents control their position relative to a designated leader to meet formation requirements [1315]. Artificial potential fields have similarly been shown effective as a construct to establish formation-keeping forces between robots within a group [16, 17]. Cluster space, an approach that allows for intuitive specification of formation characteristics and implements control directly on these variables, has also been demonstrated successfully for a number of robotic systems [18]. Current trends in research, however, indicate a focus on the incorporation of formation requirements into the framework of optimal control, and will be discussed in this chapter.

Due to the inherent physical distribution of agents and the potential for limited information exchange, decentralized control protocols for multirobot systems are popular. However, centralized architectures, which exploit global information, are more amenable to executing specific time-varying formation trajectories. The latter pertains to a class of similar methods highly relevant to this chapter that delegate path design to an earlier step, relying on motion planning to avoid inter-agent collisions and achieve varying degrees of coordination [1924]. Distinguished among these is [25], which frames motion coordination as a velocity-optimization problem. Formations are defined by robot-pair relative geometries as a function of distance along their respective paths, forming a constraint net. Optimal trajectories for each robot are then generated such that these formation errors are minimized. Alternatively, [26] represents the set of robot positions at a particular time as a 2D planar curve, and develops a synchronization controller that regulates robot motions to simultaneously track the prescribed formation boundaries as well as their individual paths. Although an optimal velocity signal is not derived, as in [25], the model allows for complete specification of any formation over time, provided the potentially complicated individual robot paths are attainable. For a number of conceivable formations, this is a non-trivial step and can prove prohibitive. The methods proposed in this chapter, which build from the cluster space approach to multirobot system specification, address this issue.

In contrast to the investigations discussed above, much of current research in multirobot systems is dedicated to the use of distributed optimal control techniques. These are appropriate for applications that permit simple formation specification where robots must operate with communication restrictions and local information such as relative positioning. Consensus algorithms, which draw from concepts in distributed computing and graph theory, are present in many of these approaches [2729]. In the context of a cooperative multivehicle system, information consensus refers to the convergence of agents in a networked system to a common task or variable such as the center of a formation shape, the rendezvous time, or the direction of formation translation [30]. Also of note are distributed control-based methods to handle swarms, or multiscale dynamical systems, which are comprised of many agents [3134]. In general, these techniques are only capable of assigning coarse-grained dynamics; specific paths and distributions are not determined a priori. Each unit is held subject to local objectives and constraints, giving rise to certain coherent macroscopic behaviors. For example, Ferrari et al. [35] model global behavior of a multiagent system using PDFs and optimizes subject to coupled local agent dynamics in such a manner that cohesion is achieved and the result requires far less computation than classical optimal control.

Energy efficiency in mobile robotics systems is of great concern given that energy sources are often carried, and practical applications require extended remote operation wherein limited resources must be conserved. Many investigations seek to address this issue through the use of motion planning techniques to reduce the energy consumption in system components. Typically, proposed energy models are incorporated into optimal control frameworks to derive trajectories that minimize energy expenditure [3640]. For example, in a recent work, Liu and Sun [41] decompose energy consumption into three categories: kinetic energy transformation, overcoming traction resistance, and maintenance of electrical sources for the operation of sensors, on board PCs, and control circuits. This analysis is then used to generate both an energy optimal path and a velocity trajectory, which further conserves energy. While a complete and detailed energy model can be beneficial, it is well known that preventing large torque variations in motors by smoothing velocity profiles is most fundamental to energy conservation [42, 43]. This chapter concentrates on minimizing energy expenditure for a formation of mobile robots in this regard.

The investigations referenced above are geared toward individual robots and therefore do not adequately address the optimal planning of energy-efficient trajectories for multiagent systems where a holistic approach is appropriate. There are, however, a number of methods that include provisions for minimizing aggregate energy consumption. For example, Sieber et al. [44] formulate an LQR-like optimal control problem designed to move a formation of mobile robots to a goal while minimizing input energy and incorporating a provision for formation rigidity into the cost functional. Similarly, Wigstrom and Lennartson [45] generated trajectories that reduce energy consumption using pseudo-spectral optimal control, though paths are considered free. Coverage algorithms such as [40, 46] also implement energy conservation constraints while maximizing the reach of mobile robot networks and sensing. A few swarm-like methods have accounted for power consumption as well, but they minimize global energy in order to achieve stability and cohesion for the group, or to affect the size and internal coverage of the swarm [47, 48]. While these examples address the conservation of group energy, they do not deal with the generation of smooth energy-efficient velocity trajectories along predefined paths, an objective of this chapter.

The concepts of time and energy optimality in the context of trajectory generation for multirobot systems are well represented in the literature. However, they are largely accounted for alongside formation constraints, thus the derived control signals are suboptimal with regard to time and/or energy exclusively. To our knowledge, there are no methods that achieve high precision time-varying maneuvers and successfully separate the generation of optimal trajectories for each robot in a multiagent group from formation requirements. The techniques proposed in this chapter address this shortcoming.

The contribution of this investigation is a method to generate continuous force, acceleration, and velocity profiles for a formation of mobile robots with predetermined paths, while time and energy are minimized in chosen proportions. Previously proposed methods with similar objectives have employed optimization techniques with robot level dynamic constraints and formation level cost functions. In contrast, our treatment uniquely optimizes and imposes constraints at the cluster or formation level, with favorable results. Further advantages of our technique are explained in Section 4.

We first introduce the cluster space control framework, which presents a group of mobile robots as a virtual articulating mechanism in order to facilitate characterization and to implement coordinated control of the system. A parameterization of the cluster dynamic equations is next proposed which results in a reduced second-order state space model. The structure and numerical solution of the optimization are then shown. Finally, a simulation of a three-robot cluster controller is used to verify and validate the solution trajectory, after which analysis and results are presented.

2. Cluster space

2.1. Cluster space specification of multirobot systems

The cluster space control framework conceptualizes a multirobot system as a single entity, a cluster, which is described in terms of its global position and orientation, shape, and the relative orientations of individual robots within the cluster. Based on these attributes, a set of independent state variables is defined to specify, control, and monitor the position and motion characteristics of the formation [18]. These quantities can be mathematically related to the positions and velocities of the robots in the group through a formal set of kinematic transforms, much like the end-effector position and velocity of a robotic manipulator can be related to its joint angles and rotational velocities. Similarly, a set of cluster dynamic equations of motion have been defined with coefficients that are a function of dynamic properties of individual robots, allowing generalized forces in cluster space to be related to generalized forces in robot space [49]. These relationships enable the use of a feedback formation control system in which the operator can command the path(s) of a multirobot formation with respect to the cluster states, and be relieved from the task of specifying individual robot motions.

Cluster space represents a natural point of view for the operator suited for specifying well-behaved, smooth, formation state trajectories [50]. Unlike other formation control approaches that must commit to centralized or decentralized protocols, the cluster space framework accommodates a range of (de)-centralization architectures through the selection of cluster state space variables [51]. Cluster control has been experimentally demonstrated with groups of two to six robots, operating on/in land/sea/air, with both piloted and automated controls, and with a variety of compensation strategies. Ongoing work includes use of the technique for real-world applications such as gradient-based adaptive environmental sampling [52], object tracking [53], object transportation [54], and escorting in the presence of long-distance communications [55, 56].

2.2. Description of a three-robot cluster

Previous work on the cluster space state representation of a mobile multirobot system presented a generalized framework for a system of n robots each with m degrees of freedom [1]. In this study, we will consider the implementation of a group of three planar robots each with 3 degrees of freedom: two translational (x1, y1, x2, y2, x3, y3) and one rotational (θ1, θ2, θ3). These variables are referenced to a global frame and constitute the robot space description of the pose of the system, r. Alternatively, the pose of the system in cluster space can be defined by a position vector c consisting of variables that characterize the globally referenced cluster location and orientation at the formation centroid (xc, yc, θc), the geometry of the three-robot triangular formation (p, q, β), and the relative rotations of the individual robots within the cluster (φ1, φ2, φ3). In general, we note that the cluster space control framework provides flexibility in the location of the cluster frame and in the selection of shape variables; for the example used in this study, the shape variables (p, q, β) represent a side-side-angle definition of the three-robot cluster. A depiction of both robot space and cluster space variables is provided in Figure 1.


Figure 1.

State space variables for a three-robot cluster.

2.3. Cluster space equations of motion

In previous work, successful cluster space control has been demonstrated through the use of a kinematic, or resolved rate, control approach in which the operator specifies desired cluster velocities, which are then converted into robot velocity commands through an inverse-Jacobian transform. This has been adequate for a number of demonstrations and applications, particularly when the robots have on-board velocity controllers, are heavily damped, and when external disturbances are minor. For more challenging cases, a dynamic cluster space controller was developed, based on the definition of cluster equations of motion. This dynamic model describes the interdependence between the positions, velocities, and accelerations of the cluster state variables and the generalized forces and torques acting on the cluster. It contains coefficients that can be mathematically related to similar coefficients in robot space dynamic equations. The details of this derivation using Lagrange formalism are presented in [54]. The resulting cluster space dynamic equation follows:


where if n is the number of robots in the cluster and m the number of degrees of freedom of each robot: F ε Rn is an nm × 1 vector of cluster generalized forces and torques belonging to a set defined {F | Fimin ≤ Fi ≤ Fimax, i = 1 : nm}; Λ(c) is an nm × nm symmetric, positive definite, cluster mass or inertia matrix of the quadratic form; cmedia/eq1.png and its first and second derivatives ċc̈media/eq2.png are nm × 1 vectors of cluster space state positions, velocities, and accelerations, respectively; μcċmedia/eq3.png is an nm × 1 vector of cluster space Centrifugal and Coriolis forces; g(c) is an nm × 1 vector of gravity forces in cluster space.

The cluster space equations of motion were derived using a Lagrangian formulation based on the formation’s potential and kinetic energy. An alternate dynamic form for a second-order system can also be realized through a quadratic representation of the first-order cluster velocity product terms [49]:


This version is obtained through the use of Christoffel symbols (Γjkic), which are derived from the cluster mass matrix Λ(c), where B is an nm × nm × nm vector of Christoffel symbols:

And Γjkic is an nm x nm symmetric matrix for i, j, k = 1 to nm:


This form has the desired quality of being conducive to state parameterization, a necessary conversion due to the high dimensionality of the cluster state vector and equations of motion. It does not include a gravity term due to the fact that our analysis is specific to planar rovers whose gravity force is canceled out by the force normal to the surface.

2.4. Cluster space parameterization

The cluster space state vector for a formation of n robots each with m degrees of freedom is of size nm, which for the presented three-robot example corresponds to a nine-element state vector. The application of optimal control techniques to a cluster state vector of this size would result in a 2-pt boundary (shooting) problem of large order requiring an unmanageable computational effort. We therefore seek to reduce the dimensionality of the control problem and its numerical solution by defining a one-dimensional path space denoted as s(t) (where s = [0,1]), representing the distance traveled along a specified path. The following draws from the general methodology presented in [58].

The cluster state vector, at a given time, specified as a function of the distance traveled along the path, and its first and second derivatives taken w.r.t. t are given by


where fs is the unit vector tangent to the path, fss is the curvature, ṡmedia/eq5.png is the speed along the path, and s̈media/eq6.png is the acceleration. Substituting these expressions for c, ċmedia/eq7.png, and c̈media/eq8.png in Eq. (2), we obtain


If we let m(s) = Λ(s)fs and bs=Λsfss+fsTBfs :

Using Eq. (8) we have rewritten the cluster dynamics in terms of the velocity ṡmedia/eq5.png and acceleration s̈media/eq6.png along the cluster state paths where m(s) and b(s) are the coefficients of acceleration and Coriolis/Centripetal forces, respectively, expressed in cluster path coordinates. It is evident in the transformed dynamics that a linear relationship exists between F and s̈media/eq6.png. This mapping is unique; therefore, we can use ṡmedia/eq5.png as the control input, effectively reducing the 2nm-dimensional state space to two independent states, ṡmedia/eq5.png and s̈media/eq6.png [59]. (Note: The coefficient matrices m(s) and b(s) are both of size 9 × 9; each element is an expression of a size that precludes its presentation here.)

Now that we have represented the cluster dynamics in path space, inequality constraints on the magnitude of the cluster force, {Fi min ≤ Fi ≤ Fi max, i = 1 : nm} can also be converted. Substituting (8) into this expression yields nm path space inequality expressions for cluster space velocity and acceleration constraints:


The bounds on the path acceleration and velocity at a given point are


where assuming mi ≠ 0 and mjbi − mibj ≠ 0:


Again, these derivations originate in [58, 59]. By virtue of the similarity between cluster space dynamics with that of manipulators, the form of the inequality constraints is identical. They have been presented here for completeness; however, the simulations in Section 4 will not consider trajectories in which they are violated as it is outside the scope of our analysis. Furthermore, a motivating factor behind the inclusion of energy in the minimization is to depart from time-optimal trajectories and reduce the strain on robot actuators. This purpose would be defeated if robot acceleration and velocity bounds were reached.

3. Cluster space time-energy optimal control

3.1. Problem formulation

To minimize, in varying proportions, the energy and motion time of system (8) along a specified cluster path, we formulate and solve the following optimization problem. The parameterization of the cluster dynamics reduces its state space to the double integrator:


The objective function, denoted as J, incorporates free final time and a weighted cluster energy term:


where L(xu) = 1 + media/eeq1a.png2F2, and media/eeq1a.png ranges from 0 to 1. Or, in cluster path space coordinates, substituting (8) for F:


Subject to the boundary conditions:


The state-dependent control constraints can then be defined as



umax(x)=s̈media/eq6.pngmax (ṡmedia/eq5.png, s) and umin(x)=s̈media/eq6.pngmin (ṡmedia/eq5.png, s).

And the state inequality constraints:


Computing u*(t), the optimal acceleration along the path gives us access to the optimal trajectory of the full dynamic system, media/eq9.png , and c*(t) . The structure of the optimal control solution of this problem follows from the first-order necessary optimality conditions for the case of state-dependent control constraints and free final time [60]. Due to the reformulation in s, the time-energy optimal control problem is convex; therefore it can be concluded that any local optimum of the problem is also globally optimal.

3.2. Structure of the optimal control solution

The optimal control (u*) and states x*media/eq10.png must satisfy the following conditions [59]:

For all t ϵ [t0tf] , where the Hamiltonian and costates are given by


Expanded using (15) and (17):


The subscript ‘s’ denotes partial derivatives with respect to s = x1. The state-dependent control constraints, gxu=g1xu,g2xuTmedia/eq11.png, are incorporated into the Hamiltonian using the multipliers μ=μ1μ2Tmedia/eq12.png. They are positive if the associated constraint (dictated by (22)) is active and zero otherwise, ensuring that the cost function can only be reduced by violating the constraints [59].

Solving Hu = 0 for u yields the unconstrained optimal control signal:


This equation is valid if the control constraints are inactive. If they are activated, the optimal control switches to the bounds umax(t) or umin(t):


3.3. Numerical solution

The control signal u = x2 is found by solving a fourth-order two-point boundary value problem given by Eqs. (17), (28), and (29):


If we assume initial unconstrained control, substitute initial condition x2(0) = 0 into (26), and apply conditions (22) and (23), we can solve for the initial value of one of the costates:


We now have initial conditions for all necessary variables with the exception of λ1(0). The initial condition for λ1 must therefore be iterated, or guessed at until the correct final conditions are realized for x1 and x2. This numerical problem can be solved in a computationally inexpensive manner.

4. Results and analysis

The numerical methods presented in the previous sections were implemented to obtain time-energy optimal trajectories for the cluster paths presented in this section. Subsequently, a cluster space kinematic controller [18] was used to simulate the tracking of desired cluster paths and motions in the following examples for three-robot cluster rotate and translate as well as rotate and resize maneuvers.

4.1. Rotate and translate simulation

This cluster path is achieved by commanding translation from (xc,yc) = (0,0) to (xc,yc) = (10,10) and simultaneous formation rotation from θc = 0 to π, with initial (cinit) and path-parameterized cluster state vector (f(s)):


The following are depictions of the cluster parameterized phase plane and path velocity vs. time for multiple values of media/eeq1a.png (Figure 2):


Figure 2.

Cluster parameterized phase plane for multiple media/eeq1.png.

Upon inspection, it is apparent that the generated plots conform to intuition regarding the expected shape of an energy optimal velocity profile. Given that generally steep acceleration results in excessive energy expenditure one expects that a mobile robot would increase its speed gradually (nonlinearly) up to a peak, after which it should identically decelerate. The velocity profile should therefore be parabolic, symmetric, and continuous, unless state constraints were violated, producing a plateau (trapezoidal) effect with discontinuities at the switching point. In [61], velocity profiles that match this description were generated while minimizing total energy drawn from the batteries of a particular mobile robot. Their results, given different motor characteristics, ranged from the widely used trapezoidal profile to the parabolic profile observed in the simulation.


Figure 3.

Velocity along the cluster parameterized path for multiple media/eeq1.png.

Comparison of the optimal velocity profiles for different media/eeq1a.png in Figure 3 confirms the anticipated result that increasing values of media/eeq1a.png, and therefore energy contribution to the cost function, results in velocity profiles of reduced average magnitude and longer duration. In Figure 2, phase planes generated from successively smaller media/eeq1a.png increase in magnitude as they approach the time optimal trajectory. The time-optimal boundary, though not derived as part of this study, can be determined by calculating the maximum (minimum) parameterized cluster velocity and acceleration achievable at each possible cluster configuration along the given path. However, for a small enough choice of media/eeq1a.png, the generated velocity profile will sufficiently approximate this limit.

The trajectory obtained, using ε = .5, was executed using the simulation referenced above, to yield the snapshots in Figure 4 of the cluster in 5-s intervals.

Notice that the paths of robots 1 and 2 (the blue and red dots, respectively) and robots 2 and 3 (the red and green dots, respectively) intersect during the course of the maneuver, indicating a need for timing constraints to avoid collision. There are methods that define multirobot coordination in this manner, referenced earlier [19, 39], that generate robot velocity profiles from given paths such that robots avoid collision. Cluster space requires no such direct provision, the timing of individual robot trajectories both to avoid inter-robot collision and maintain formation is handled implicitly. This is evident in Figure 5, which depicts the distinct optimal velocity profiles of each robot obtained by applying the cluster inverse kinematic transformations to the optimal parameterized velocity. They are of equal duration yet their dissimilar contours and therefore areas indicate unequal distances traveled. Additionally, due to the fact that optimizing in cluster space relieves us from imposing an explicit formation constraint in the cost function as in [25, 26], the mathematical treatment can be dedicated exclusively to optimizing time and energy.


Figure 4.

Snapshots of cluster rotate and translate maneuver in 5-s intervals.


Figure 5.

Individual robot velocity profiles.

4.2. Rotate and resize simulation

Another example of a cluster maneuver, rotate and resize, is obtained by commanding rotation from θc = 0 to π and a simultaneous resize from p, q = 10 to p, q = 20, with initial (cinit) and path-parameterized cluster state vector (f(s)):


The following are depictions of the cluster parameterized phase plane and path velocity vs. time for multiple values of media/eeq1a.png (Figure 6):


Figure 6.

Cluster parameterized phase plane for multiple media/eeq1.png.


Figure 7.

Velocity along the cluster parameterized path for multiple media/eeq1.png.

As with a rotate and translate case, increasing media/eeq1a.png lengthens the duration of the trajectory and flattens the shape of the optimal velocity profile (Figure 7), suggesting reduced energy expenditure. Additionally, the phase plane of Figure 6 appears to approach a time-optimal limit with decreasing media/eeq1a.png, as anticipated. However, comparison with Figure 2 of the general shape and relative location of the peak velocity reveals a discernable difference. The rotate and resize profile exhibits a skew toward the velocity axis resulting in a peak magnitude that occurs before the half-time trajectory point, while the rotate and translate profile is approximately symmetric about the half-time point. This effect can be explained by viewing the cluster as a virtual articulating mechanism possessing inertia. Because the cluster inertia grows as the path is followed, optimizing in cluster space produces a velocity profile that favors torque application early in the maneuver. It is also true then that the symmetric nature of the optimal velocity profile in a case such as a cluster rotate and translate often implies a constant or symmetric inertia throughout the trajectory.


Figure 8.

Snapshots of cluster rotate and resize maneuver in 5-s intervals.

The trajectory simulation for ε = . 5 was executed to yield the following snapshots of the cluster in 5-s intervals (Figure 8):

The individual robot velocity profiles for this case (not pictured here) are identical due to the fact that their paths do not intersect and the chosen cluster geometry is an equilateral triangle, implying equidistant paths. Therefore, in contrast to Figure 5, this maneuver does not require a provision for timing to avoid inter-agent collision. A virtue of our technique is that optimizing trajectories in cluster space removes the operator from this consideration and handles both scenarios without intervention.

4.3. Time-energy tradeoff

As previously acknowledged, adjusting the weight of the energy term in the objective function results in varying duration times and energy expenditures. In order to thoroughly investigate the trade-off range, optimal solutions were obtained for a number of media/eeq1a.png values in the rotate and translate case. Figure 9 depicts the relationship between trajectory duration (T) and the cluster energy as represented in the objective function, 0tfF2dt, for media/eeq1a.png ranging from .001 to .01. The results, normalized to media/eeq1a.png = .001, show that for a 10% increase in T, energy expenditure is reduced by 22.5% (point (a) in Figure 9). As media/eeq1a.png gets larger, and T is increased further by 10%, energy is reduced by 19.8% (point (b) in Figure 9). The slope of this curve will of course change with cluster path and trajectory; however, we expect to always observe diminishing reductions in energy expenditure with increments of T, as we have with this case. In general, for a given cluster and trajectory, this plot can be generated and used as a tool to inform the appropriate choice of media/eeq1a.png given mission requirements such as time to completion or energy limitations.

5. Conclusion


Figure 9.

Energy vs. trajectory duration.

This chapter presented a technique to generate a time-energy optimal trajectory for a cluster of mobile robots with predetermined paths. The method is uniquely applied in a parameterized formation state space and incorporates the nonlinear dynamics of the cluster and actuator constraints to enable intuitive optimal trajectory planning for time varying formations. Simulation results verified the generated trajectories and demonstrated the advantages of using a time-energy tunable objective function. The ability to choose more energy-efficient trajectories reduces the strain on actuator components and energy reserves, thereby promoting longevity in both. The tool in Figure 9 also demonstrates that the operator has access to a substantial path-specific time/energy range, within which one must choose a mission-appropriate combination.

We plan to incorporate several extensions to this work in the future. First, we will integrate cluster space obstacle avoidance [62] into the optimal trajectory-tracking controller. In addition, we will develop cluster space velocity and acceleration bounds to include the characterization of a velocity limit curve as well as a phase plane description of the admissible range. With these bounds, which are a function of the cluster states and are therefore variable in the choice of path, one could derive the time optimal cluster trajectory, approximated with small media/eeq1a.png in the simulations of the previous section. We will also attempt to address practical issues such as friction, gravity, and motor dynamics into the formulation in order to make the technique more applicable to a wide range of multirobot systems. Finally, we will experimentally verify and validate the technique with several existing multirobot experimental test beds, to include terrestrial rovers, surface and underwater marine vehicles, and aerial vehicles.


1 - D. Kingston, R.W. Beard, R.S. Holt, “Decentralized Perimeter Surveillance Using a Team of UAV’s,” IEEE Transactions on Robotics, vol. 24, no. 6, pp. 1394–1404, 2008.
2 - J. Hu, L. Xie, J. Xu, “Vision-based Multi-Agent Cooperative Target Search,”, Control Automation Robotics & Vision 12th International Conference, pp. 895–900, 2012.
3 - J. Dong, E. Nelson, V. Indelman, N. Michael, F.Dellaert, “Distributed Rel-time Cooperative Localization and Mapping using an Uncertainty-Aware Expectation Maximization Approach,” IEEE International Conference on Robotics and Automation, pp. 5807–5814, 2015.
4 - Y. Chen, X.C. Ding, A. Stefanescu, C. Belta, “Formal Approach to the Deployment of Distributed Robotic Teams,” IEEE Transactions on Robotics, vol. 28, no. 1, pp. 158–171, 2012.
5 - Y. Xu, J. Choi, S. Oh, “Mobile Sensor Network Navigation Using Gaussian Processes With Truncated Observations,” IEEE Transactions on Robotics, vol. 27, no. 6, pp. 1118–1131, 2011.
6 - Z. Yao, K. Gupta, “Distributed Roadmaps for Robot Navigation in Sensor Networks,” IEEE Transactions on Robotics, vol. 27, no. 5, pp. 997–1004, 2011.
7 - F. Pasqualetti, A. Franchi, F. Bullo, “On Cooperative Patrolling: Optimal Trajectories, Complexity Analysis, and Approximation Algorithms,” IEEE Transactions on Robotics, vol. 28, no. 3, pp. 592–606, 2012.
8 - S.L. Smith, M. Schwager, D. Rus, “Persistent Robotic Tasks: Monitoring and Sweeping in Changing Environments,” IEEE Transactions on Robotics, vol. 28, no. 2, pp. 410–426, 2012.
9 - A. Macwan, G. Nejat, B. Benhabib, “Target-Motion Prediction for Robotic Search and Rescue in Wilderness Environments,” IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, vol. 41, no. 5, pp. 1287–1298, 2011.
10 - H. La, T. Nguyen, T.D. Le, M. Jafari, “Formation Control and Obstacle Avoidance of Multiple Rectangular Agents with Limited Communication Ranges,” IEEE Transactions on Control of Network Systems, 99, pp. 1–1, 2016.
11 - S.A. Reveliotis, E. Roszkowska, “Conflict Resolution in Free-Ranging Multi-vehicle Systems: A Resource Allocation Paradigm,” IEEE Transactions on Robotics, vol. 27, no. 2, pp. 283–296, 2011.
12 - H. M. La, R. S. Lim, J. Du, S. Zhang, G. Yan, W. Sheng. Development of a Small-scale Research Platform for Intelligent Transportation Systems, IEEE Transactions on Intelligent Transportation Systems, vol. 13(4), pp.1753–1762, Dec. 2012
13 - F. Li, Y. Ding, K Hao, “A Dynamic Leader-Follower Strategy for Multi-robot Systems,” IEEE International Conference on Systems, Man, and Cybernetics,” pp. 298–303, 2015.
14 - A. Loria, J. Dasdemir, N. Alvarez Jarquin, “Leader-follower Formation and Tracking Control of Mobile Robots Along Straight Paths,” IEEE Transactions on Control Systems Technology, vol. 24, issue: 2, pp. 727–732, 2016.
15 - S. Su, Z. Lin, A. Garcia, “Distributed Synchronization Control of Multiagent Systems with Unknown Nonlinearities,” IEEE Transactions on Cybernetics, vol. 46, issue: 1, pp. 325–338, 2016.
16 - L.A. Valbuena Reyes, H.G. Tanner, “Flocking, Formation Control, and Path Following for a Group of Mobile Robots,” IEEE Transactions on Control Systems Technology, vol. 23, issue: 4, pp. 1268–1282, 2015.
17 - M. M. Zavlanos, G.J. Pappas, “Potential Fields for Maintaining Connectivity of Mobile Networks,” IEEE Transactions on Robotics, vol. 23, issue: 4, pp. 812–816, 2007.
18 - C. Kitts, I. Mas, “Cluster Space Specification and Control of Multirobot Systems,” IEEE/ASME Transactions on Mechatronics, vol. 14, no. 2, April 2009.
19 - J. Peng, S. Akella, “Coordinating Multiple Robots with Kinodynamic Constraints along Specified Paths,” International Journal of Robotics Research, vol. 24, pp. 295–310, Apr. 2005.
20 - S.M. LaValle, S.A. Hutchinson, “Optimal Motion Planning for Multiple Robots having Independent Goals,” IEEE International Conference on Robotics and Automation, vol. 3, pp. 2847–2852, Apr. 1996.
21 - R. Ghabcheloo, I. Kaminer, A.P. Aguiar, A. Pascoal, “A General Framework for Multiple Vehicle Time-Coordinated Path Following Control,” American Control Conference, pp. 3071–3076, 2009.
22 - P. Abichandani, H.Y. Benson, Moshe K., “Multiple-vehicle Path Coordination in Support of communication,” IEEE International Conference on Robotics and Automation, pp. 3237–3244, 2009.
23 - T. Simeon, S. Leroy, J. P. Laumond, “Path Coordination for Multiple Mobile Robots: A Resolution Complete Algorithm,” IEEE Transactions on Robotics and Automation, vol. 18, no. 1, pp. 42–49, Feb. 2002.
24 - R. Olmi, C. Secchi, C. Fantuzzi, “Coordination of multiple AGVs in an industrial application,” Proc. IEEE International Conference on Robotics and Automation, Pasadena, CA, May 2008, pp. 1916–1921.
25 - L. Shuang, D. Son, “Coordinated Motion Planning for Multiple Mobile Robots Along Designed Paths With Formation Requirement,” IEEE/ASME Transactions on Mechatronics, vol. 16, Issue: 6, pp. 1021–1031, December 2010.
26 - D. Sun, C. Wang, W. Shang, G. Feng, “A Synchronization Approach to Multiple Mobile Robots in Switching between Formations,” IEEE Transactions on Robotics, vol. 25, no. 5, pp. 1074–1086.
27 - K.H.Movric, F. Lewis, “Cooperative Optimal Control for Multi-Agent Systems on Directed Graph Topologies,” IEEE Transactions on Automatic Control, vol. 59, issue: 3, pp. 769–774, 2014.
28 - J. Wang, M. Xin, “Integrated Optimal Formation Control of Multiple Unmanned Vehicles,” IEEE Transactions on Control Systems Technology, vol. 21, issue: 5, pp. 1731–1744, 2013.
29 - X. Sun, C.G. Cassandras, “Optimal Dynamic Formation Control of Multi-Agent Systems in Environments with Obstacles,”, IEEE Conference on Decision and Control 15, 2015.
30 - W. Ren, R.W. Beard, E.M. Atkins, “Information consensus in multivehicle cooperative control,” IEEE Control Systems, vol. 27, issue: 2, pp. 71–82, 2007.
31 - K. Elamvazhuthi, S. Berman, “Optimal Control of Stochastic Coverage Strategies for Robotic Swarms,” IEEE Conference on Robotics and Automation 26, 2015.
32 - C. C. Cheah, S. P. Hou, J. J. E. Slotine, “Region-based Shaped Control for a Swarm of Robots,” Automatica, vol. 45, no. 10, pp. 2406–2411, 2009.
33 - S. D. Bopardikar, F. Bullo, J. P. Hespanha, “A Cooperative Homicidal Chauffeur Game,” Automatica, vol. 45, pp. 1771–1777, July 2009.
34 - H. Duan, Q. Luo, Y. Shi, “Hybrid Particle Swarm Optimization and Genetic algorithm for multi-UAV Formation Reconfiguration,” IEEE Computational Intelligence Magazine, vol. 8, issue: 3, 2013.
35 - S. Ferrari, G. Foderaro, P. Zhu, T. A. Wettergren, “Distributed Optimal Control of Multiscale Dynamical Systems: A Tutorial,” IEEE Control Systems, vol. 36, issue: 2, 2016.
36 - A. Barili, M. Ceresa, C. Paris, “Energy-saving Motion Control for an Autonomous Mobile Robot,” Proceedings of the IEEE International Symposium on Industrial Electronics, vol. 2, pp. 674–676, 1995.
37 - A.A. El-satte, S. Washsh, A.M. Zaki, S.I. Amer, “Efficiency-optimized Speed Control System for a Separately-excited DC motor,” Proceedings of the IEEE International Conference on Industrial Electronics, Control, and Instrumentation, vol. 1, pp. 417–422, 1995.
38 - Y. Mei, Y.H. Lu, Y.C. Hu, C.S.G. Lee, “Energy-efficient Motion Planning for Mobile Robots,” Proceedings of the IEEE International Conference on Robotics and Automation, vol. 5, pp. 4344–4349, 2004.
39 - W. Weigui, C. Huitang, W. Peng-Yung, “Optimal motion Planning for a Wheeled Mobile Robot,” Proceedings of the IEEE International Conference on Robotics and Automation, vol. 1, pp. 41–46, 1999.
40 - Y. Mei, Y. Lu, Y.C. Hu, G. Lee, “Deployment of Mobile Robots with Energy and Timing Constraints,” IEEE Transactions on Robotics, vol. 22, pp. 507–522, 2006.
41 - S. Liu, D. Sun, “Minimizing Energy Consumption of Wheeled Mobile Robots via Optimal Motion Planning,” IEEE/ASME Transactions on Mechatronics, vol. 19, issue: 2, pgs. 401–411, 2014.
42 - A. M. Hussein, A. Elnagar, “On Smooth and Safe Trajectory Planning in 2D Environments,” in Proceedings of IEEE International Conference on Robotics and Automation, 1997, vol. 4, pp. 3118–3123.
43 - M. Yongguo, L.Y. Hsiang, Y. Hu, C.S.G. Lee, “A Case Study of Mobile Robot’s Energy Consumption and Conservation Techniques,” 12th International Conference on Advanced Robotics, pp. 492–497.
44 - D. Sieber, F. Deroo, S. Hirche, “Optimal Dynamic Formation Control of Multi-Agent Systems in Environments with Obstacles,” IEEE Conference on Decision and Control, Dec. 15, 2015.
45 - O. Wigstrom, B. Lennartson, “Towards Integrated OR/CP Energy Optimization for Robot Cells,” IEEE International Conference on Robotics and Automation, June 7, 2014.
46 - G. Wang, M.J. Irwin, P. Berman, F. Haoying, T. La Porta, “Optimizing Sensor Movement Planning for Energy Efficiency,” Proceedings of the 2005 International Symposium on Low Power Electronics and Design, pp. 215–220, 2005.
47 - H.J. Chang, G.C.S. Lee, Y. Lu, Y. Hu, “Energy-Time-Efficient Adaptive Dispatching Algorithms for Ant-Like Robot Systems,” Proceedings of the IEEE International Conference on Robotics and Automation, vol. 4, pp. 3294–3299, 2004.
48 - R. Pedrami, B.W. Gordon, “Temperature Control of Energetic Swarms,” International Conference on Mechatronics and Automation, pp. 2639–2644, 2007.
49 - I. Mas, C. Kitts, R. Lee. “Dynamic Control of Mobile Multirobot Systems: The Cluster Space Formulation,” Access, IEEE, pp. 558–570, 2014.
50 - C. Kitts, P. Mahacek, T. Adamek, I. Mas. “Experiments in the Control and Application of Automated Surface Vessel Fleets.” Proceedings IEEE/MTS Oceans Conference, pp. 1–7, 2011.
51 - I. Mas, C. Kitts, “Centralized and Decentralized Multi-Robot Control Methods using the Cluster Space Control Framework.” IEEE Conference on Advanced Intelligent Mechatronics, pp. 115–122, 2010.
52 - P. Mahacek, T. Adamek, V. Howard, K. Rasal, C. Kitts, B. Kirkwood, G. Wheat. “Cluster Space Gradient Tracking – Control of Multi-Robot Systems.” Proceedings ASME Information Storage and Processing Systems Conference, Santa Clara CA, June 2011.
53 - S. Dayanidhi, R. Beetem, C. Kitts, “Initial Experiments in Multirobot-Based Tracking Networks,” ASME-ISPS/JSME-IIP Joint International Conference on Micromechatronics for Information and Precision Equipment, 2012.
54 - I. Mas, C. Kitts, “Multi-Robot Object Manipulation Using Cluster Space Control,” 2010 ASME Information Storage and Processing Systems Conference, 2010.
55 - P. Mahacek, C. Kitts, I. Mas, “Dynamic Guarding of Marine Assets Through Cluster Control of Automated Surface Vessel Fleets.” IEEE/ASME Transactions on Mechatronics, vol. 17, no. 1, pp. 65–75, 2012.
56 - I. Mas, S. Li, J. Acain, C. Kitts, “Entrapment/Escorting and Patrolling Missions in Multi-Robot Cluster Space Control.” Proc IEEE International Conference on Intelligent Robots and Systems, pp. 5855–61, 2009.
57 - H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, S. Thrun, “Principles of Robot Motion – Theory, Algorithms, and Implementations,” Cambridge, MA, The MIT Press, 2005, pp. 353–356.
58 - Z. Shiller, H. Lu, “Computation of Path Constrained Time Optimal Motions With Dynamic Singularities,” Transactions of the ASME Journal of Dynamic Systems, Measurement, and Control, vol. 114, no. 1, pp. 34–40, 1992.
59 - Z. Shiller, “Time-Energy Optimal Control of Articulated Systems with Geometric Path Constraints,” Transactions of the ASME. Journal of Dynamic Systems, Measurement and Control, vol. 118, no. 1, pp. 139–143, March 1996.
60 - A.E. Bryson, Y.C. Ho, “Applied Optimal Control, Optimization, Estimation and Control,” Hemisphere Publishing, New York, 1975.
61 - C. Kim, B. Kim, “Minimum-Energy Translational Trajectory Generation for Differential-Driven Wheeled Mobile Robots,” Journal of Intelligent Robotic Systems, vol. 49, pp. 367–383, 2007.
62 - I. Mas, C. Kitts. “Obstacle Avoidance Policies for Cluster Space Control of Non-holonomic Multi-Robot Systems,” IEEE/ASME Transactions on Mechatronics, vol. PP, no. 99, pp. 1–12, 2011.