Planning for Formations of Motion-Constrained Vehicles

Approach and Motivation

Many computer games and simulations involve the modeling of agents, such as airplanes and boats, which have to move in formation to reflect the behavior of their real world counterparts. For example, military games can utilize formations to move teams of airplanes before attacking a user specified target. This research is especially motivated by training simulations for military officers, which must model realistically the maneuvers of opposing and friendly aircraft and boats. The need to model formations arises as a primary requirement during the development of such simulations. Beyond computer games and simulations Formations can be useful in robotic space exploration, where multiple satellites and spacecraft can provide improved reliability, and military applications, where formations were originally developed and can be utilized by unmanned vehicles. They can also provide reduction in induced drag to aircraft flying in a vee formation, thus, extending the range of a squadron or allowing solar powered airplanes to stay aloft longer.

The objective is to maintain a static formation defined over curvilinear coordinates, which are a coordinate system in which the coordinate lines may be curved. The formation is defined relative to a reference agent. An illustration of a formation along curvilinear coordinates is shown above.

If airplane L is the leader,then the middle blue line corresponds to the 'x' axis of the curvilinear system, and the line perpendicular to the airplane is the 'y' axis. To maintain a static formation, each follower aircraft must maintain p_i distance along the leader's curved trajectory and q_i distance along the perpendicular direction, as in the figure above. Finally, the variable d_L denotes the distance the reference agent has covered and s_i = d_L + p_i denotes the distance that the projection of follower i has covered along the leader's trajectory.

Respecting the Control Limits

There is an important issue that arises when the leader’s trajectory is computed in real time. It is possible that the controls for the follower will violate the control limits for the vehicle. In the following picture, the green lines represent the controls of the aircraft when there is no consideration of the motion limitations (represented by the red horizontal lines). The blue lines represent the result of our work, where the formation is maintained while the constraints are also respected.

Dynamic Formations

Allowing the shape of the formation to change over time might be desirable for multiple reasons. For instance, the user might want to change the formation or the team might have to fit through a small opening. Dynamic formations can also be useful for assembling a static formation from a random configuration. To achieve dynamic formations, the approach allows the coordinates [p, q] to be functions of time or distance along the leader’s trajectory.

Acquiring a Formation

This work addresses the general case, illustrated in the figure below, where the follower is not in formation with the leader. The objective is to come up with the equations of motion that will bring the follower into a desired static formation with parameters [p, q]. The idea is to define the curve the follower must follow by employing interpolation in curvilinear coordinates between its current configuration and a configuration that satisfies the formation parameters. Such a process can be achieved with the Hermite curve interpolation, which interpolates between two points P1 and P4, while respecting the tangent vectors R1 and R4 at these points respectively.

Multi-Level Formation Roadmaps for Dynamic Collision Avoidance

Teams of robots can utilize formations to accomplish a task, such as maximizing the observability of an environment while maintaining connectivity. In a cluttered space, however, it might be necessary to automatically change formation to avoid obstacles. This work proposes a path planning approach for non-holonomic robots, where a team dynamically switches formations to reach a goal without collisions. The method introduces a multi-level graph, which can be constructed offline. Each level corresponds to a different formation and edges between levels allow for formation transitions. All edges satisfy curvature bounds and clearance requirements from obstacles.

Given an environment with static obstacles (1), a collision-free roadmap G(V,E) for a holonomic system (2) can be computed using various alternatives, such as sampling-based planners. The input graph must satisfy the typical requirements of a roadmap, be directed graph and it is desirable to have a sparse roadmap and maximize distance from the obstacles. The roadmap should contain paths with obstacle clearance that satisfies the requirements of the least conservative formation, at least two nodes with more than three edges, else it will be a line or a loop graph, that robots would not be able to change their direction along the graph. Once the input graph is available, Fs copies are created for the different levels, each one corresponding to a specific static formation (3). It is necessary to edit each level so that it satisfies curvature constraints arising from the corresponding formation (4). The graph still may not satisfy collision avoidance requirements. The initial graph is computed only for one agent. Each formation requires a different clearance around the leader’s configuration. Thus, additional parts of the graph must be pruned. The clearance along edges computed given the corresponding formation for each level. The clearance on the right side of the leader can be different than the clearance on the left side depending the formation. The parts of the graph that don’t satisfy the minimum clearance are pruned. The input graph is directed, which means that for an asymmetric formation only one direction may be pruned (5). Up to this point, multiple levels for different formations have been computed. Each level is different due to different clearance and curvature limits and may also be disconnected. The capability of the team to switch between static formations is utilized so as to reconnect different graph levels. Two different types of transitions are available. The different levels can either be connected along straight edges, or through circular arcs (6). If you want to know more about the multi-level roadmap download the paper here

Using quadratic Bezier curves, a sequence of two curvature-bounded curves can be computed, which can connect any two configurations. These curves are used to connect the initial and final configuration with points on the level that corresponds to the initial/final formation respectively. The experiments evaluate the percentage of desired formation maintenance and the length of the path. Green path: the robots have to use the specific formation as much as they can. Red path: the robots can switch formations in order to return the shortest path.

Results

The following pictures provide the error between the desired formation and the achieved formation at each simulation step. The left picture displays the distance from ground truth, while the right figure shows the difference in orientation.

The next set of pictures provide the error for the dynamic formation(left picture) and the acquisition of a formation(right picture) at each simulation step. The error is the distance between the desired formation and the achieved formation.


Related Publications


People Involved