SCG Home | Department of ECE | University of Toronto | SCG Webmail
Faculty and Staff Postdoctoral Fellows and Visiting Scientists Students Alumni Graduate Laboratory SCG Seminar Series Upcoming Seminars Past Seminars SCG Technical Reports Some Recent MASc and PhD Theses Graduate Courses Graduate Programs of Study Undergraduate Courses

Multivehicle Control - Prof. M. E. Broucke

Robot

The multivehicle control lab is run by Prof. M. E. Broucke and her students using a system of 10 two-wheeled robots, pictured at right, to simulate autonomous vehicle systems. The robots were custom built for the Systems Control Group by Quanser Consulting. The control software, camera system, and vision algorithms were developed by Jacek Nawrot in his Master's thesis. The two wheels are controlled independently and allow the robots to implement experiments using unicycle dynamics.

The robots are controlled by a central server running a Java program which determines the robots actions. The robots themselves have limited on-board sensors - only wheel encoders for position and speed information. This information is augmented by position data from the overhead camera.

The robots unusual top is for the overhead camera's vision algorithm. The coloured circle is used to identify the robots and the black line is used to determine orientation.

Since the system is not truly autonomous it allows us considerable flexibility in implementing the control algorithm. The central server can be used to simulate varying degrees of autonomy allowing us to experiment about a wide range of multivehicle systems.

Pursuit Formations

Robot

This experiment is the implementation of theoretical work from Joshua Marshall's PhD thesis. He has extended the cyclic pursuit problem for point masses to more realistic nonholonomic unicycle kinematics. In the cyclic pursuit algorithm each vehicle autonomously pursues the next by actuating its steering angle (and the last pursues the first). By using this ordered pursuit strategy, Joshua showed that regular polygon formations in the plane are achievable for both constant- and varying-speed vehicles.

One possible application of this algorithm might be to engineer self-organizing robot teams. Consider, for example, a group of autonomous mobile robots, initially placed at random in a room, and suppose it is desired that they exit the room in a graceful, orderly fashion. One approach to solving this toy problem involves two steps: (i) have a supervisor issue a command to all the robots, requesting them to form a circular arrangement; then, after the robots have accomplished the first task, (ii) have the supervisor command a robot, which is close to the door, to exit, whereupon the others should follow in sequence.

random robots robots in circle formation robots leaving room

The following video presents a realization of the example problem given above. Four robots start randomly placed in a room. Using cyclic pursuit, the robots self-organize at constant speed, without supervisor intervention, into a polygon formation. Finally, a supervisor takes control of one of the robots (using a joystick) and leads the others through a door in the room.
Download MPEG ( 13 Mb )

This second experiment shows four vehicles converging to a regular polygon formation. Part way through the experiment the supervisor signals a controller gain change to the robots, demonstrating how controller gain changes affect the group's formation size and that the formation remains stationary.
Download MPEG ( 18 Mb )

For more information on pursuit problems please see the references below:

J. A. Marshall, M. E. Broucke, and B. A. Francis.  Pursuit formations of unicycles.  To appear in Automatica, vol. 41, no. 12, December 2005. (Download)
J. A. Marshall, M. E. Broucke, and B. A. Francis.  Formations of vehicles in cyclic pursuit. IEEE Transactions on Automatic Control, vol. 49, no. 11, pp. 1963-1974, November 2004. (Download)
J. A. Marshall, T. Fung, M. E. Broucke, G. M. T. D'Eleuterio and B. A. Francis.  Experimental validation of multi-vehicle coordination strategies.  In Proceedings of the 2005 American Control Conference, pp. 1090-1095, Portland, OR USA June 8-10, 2005. (Download)

Curve Shortening

Consider a smooth and closed curve lying in the plane, which does not intersect itself. If this curve is deformed along its normal vector field at a rate proportional to its curvature, the curve will become circular, and shrink to a point. This curve evolution is called the Euclidean curve shortening flow, and the result is known as the Gage-Hamilton-Grayson Theorem. In Stephen Smith's thesis, he studied the following problem: A fleet of mobile autonomous robots, lying in the plane, are numbered from 1 to n. We view the robots positions as the vertices of a polygon. The sides of the polygon are the line segments from robot 1 to robot 2, robot 2 to robot 3, and so on. How should each robot (vertex) move such that the resulting polygon evolution displays similarities to the curve shortening flow? This is depicted in the figure below. By answering this question we would solve the rendezvous problem - the problem of all robots achieving convergence to a common point - and the robots would behave in an ordered fashion as they approach their meeting point.

analogue of curve shortening
Creating a discrete analogue of the curve shortening flow.

In this work a polygon shortening flow was devised, and it was shown that: the polygon shrinks to an elliptical point; convex polygons remain convex; star formations remain as star formations; and, the perimeter of the polygon monotonically decreases to zero.

The following is a simulation of ten robots initially in a star formation following the polygon shortening flow. The dots represent the robots, and the star represents their meeting point.
Download AVI (2.85 M)
Download MPEG (3.5 M)

For more information on curve shortening as it applies to multi-agent systems please see the reference below:

S. L. Smith, M. E. Broucke, and B. A. Francis. ''Curve Shortening and its Application to Multi-Agent Systems," In Proc. IEEE Conf. on Decision and Control, Seville, Spain, Dec. 2005, to appear.

Collision Avoidance

The experiments in collision avoidance are based on theoretical work from two different Master's theses. In Farid Fadaie's Master's thesis he outlined a cooperative procedure of a least restrictive collision avoidance controller for two unicycles. To follow up this work Jacek Nawrot formulated a time optimal recovery controller for the least restrictive collision avoidance.

The least restrictive collision avoidance (LRCA) controller is said to be least restrictive in the sense that if a collision occurs using this control algorithm then it could not be avoided using any other possible control. It was proved that the LRCA controller is a bang control, i.e. it uses only a single constant control value. This algorithm was proved to be least restrictive using viablility theory.

Recovery Control

Jacek working on the robots

In Jacek Nawrot's thesis he showed that there are eight path types which are time optimal for recovery from the terminal conditions of the LRCA control. There are four distinct classes of paths, the other four being mirror images:

where: R is a right turn; L is a left turn; S is a straight segment; and B is a cycloid along the boundary the the collision region.

The combined collision avoidance and recovery control has three stages: collision avoidance, recovery of the trajectory of one vehicle, recovery of the trajectory of the other vehicle using one of the above paths.

R recovery path

The R recovery path is shown in the graphic at the right. The green paths shows action of the LRCA control for each vehicle. The blue paths shows the first stage of recovery where vehicle A, the leader, returns to it's original heading and the other vehicle B follows. The red path shows the final stage of collision recovery where vehicle B returns to it's heading following the time optimal path.

Due to the limitations of the system the control algorithm is run at a slow frequency. The slow system frequency, combined with the fact that the recovery controller is open loop means that the robots often overshoot the desired trajectory. This problem is especially apparent when the turning radius is small, since additional time turning results in a much larger heading error when the turn is tighter.

Example experiments

For more information on the LRCA controller please see the references below:

F. Fadaie and M.E. Broucke. On a Least Restrictive Collision Avoidance Controller. International Journal of Robust and Nonlinear Control. Submitted April 2005.

Jacek Nawrot. Time Optimal Control for Collision Avoidance Recovery of Two Unicycles. MASc Thesis, Systems Control Group, University of Toronto. To appear September 2005.