My research is in the
distributed control of autonomous agents. The problem of coordinated control of
a network of mobile autonomous robots, or rovers, is of interest in control and
robotics because of the broad range of potential applications: planetary
exploration, operations in hazardous environments, etc. Distributed robot
networks can potentially exhibit structural flexibility, reliability through
redundancy, and simple hardware as compared to a complex individual robot.
My primary interest is with theoretical problems associated with distributed robot networks where very simple robots have some collective capability.
As an example, consider n mobile robots moving in the plane without human supervision. In addition to a motor drive, each robot has onboard a computer and a camera with which it can see the positions of some others relative to itself. The robots are assumed not to possess GPS receivers, and there are no landmarks in view of all. Also, they are unable to communicate with each other. So it's problematic if they can meet at a common location by distributed control strategies alone. This is called the rendezvous problem . There are real situations where rendezvous is a goal, but in any event, rendezvous is the most basic formation task and therefore it's interesting from a theoretical viewpoint.
In a seminal paper, Jadbabaie et al. studied a system of “boids” moving at constant speed in the plane. Each boid has a heading angle evolving in discrete time. Also, at time t boid i can see a set of neighbours, and this leads to a time-varying visibility graph G(t) (there's an arc from node i to node j if boid i can see boid j ). Jadbabaie studied a single control strategy, namely, at time t +1 boid i changes its heading to the average heading at time t of itself and its neighbours, and he proved that all the heading angles converge to a common value (a form of rendezvous) provided G(t) has a certain connectedness property over time. What was lacking in this work was a control strategy that guarantees that, if G(t) is connected at t = 0, then it remains so for all t > 0 and rendezvous results. The circumcentre control law is one such strategy. The circumcentre control law is this: At each time t , robot i moves towards the centre of the smallest circle that surrounds it and its visible neighbours.
This pdf , adapted from a recent talk, describes some research on the rendezvous problem for point robots.
Versions of the robot rendezvous problem have also been studied extensively in computer science. There, each robot is viewed as a point in the plane. The robots are modeled as asynchronous discrete-event systems having four possible states: Wait, that is, not moving and idle; Look, during which the robot senses the relative positions of the other robots within its field of view; Compute, during which it computes its next move; and Move, during which it moves at some pre-determined speed to its computed destination. Control laws are in the form of if-then rules.
A much more interesting robot is a unicycle, the simplest wheeled robot model. With respect to a global coordinate system, it has coordinates (x,y) and a heading angle. The inputs are the forward speed and the turning rate. The rendezvous problem is much more challenging for unicycles. Rendezvous means that unicycles converge to a common point in the plane -- there is no requirement of convergence to a common heading.
The first solution of the rendezvous problem for unicycles, proving global convergence, was by Lin, Francis, and Maggiore in 2005. They assumed that the visibility graph is fixed. The rendezvous problem for unicycles with limited visibility remains an open problem.
Another distributed strategy is cyclic pursuit , where one agent pursues the next in order, and last pursues the first. Cyclic pursuit of unicycles was studied by Joshua Marshall . For these controllers, the equilibrium formations of the unicycles are generalized polygons. A deep study shows, surprisingly, that some polygon formations are stable and others not.
During recent years, a number of research groups have developed testbeds for experiments in multivehicle control. Some examples are the MIT Multivehicle Testbed, Caltech's MVWT-II Multivehicle Wireless Testbed, the Brigham Young Unmanned Air Vehicle Testbed, and the University of Illinois's Hovercraft Testbed for Decentralized Control. For our experiments, we had available a fleet of Argo Rovers, constructed at the Space Robotics Laboratory of the University of Toronto Institute for Aerospace Studies (UTIAS). Since the theoretical results of Marshall were based on ideal kinematic unicycles, an obvious question is whether the pursuit control law has more general applicability to real four-wheeled vehicles possessing nontrivial dynamics, such as the Argo Rovers. The purpose of our experiments was twofold: 1) Determine if the theoretical results of Marshall, obtained for kinematic unicycles, can be observed in practise using the four-wheeled Argo Rovers; 2) Investigate the practicality of pursuit control laws as a multivehicle coordination strategy given real hardware restrictions (e.g., processing delays, sensor limitations). Owing to limited workspace in the lab, the rovers were operated with their front and rear wheel axes ``locked'' for tightest turning. For sensing, each rover is equipped with two CCD array cameras, only one of which was used. In order for a rover to estimate the angle to its target at each instant, the rovers were colour-coded, and ordering of the vehicles was accomplished by ordering the colours. Colour detection was done by scanning the pixels in an acquired image and comparing each pixel's hue colour value with a preset target hue value.
A variety of experiments were conducted using teams of two, three, and four rovers. Despite the significant physical differences between ideal kinematic unicycles and the Argo Rover systems, the outcome was very positive. The equilibrium formations were indeed generalized regular polygons and the theoretical stability results were confirmed. Given the significant physical differences between unicycles and the Argo Rovers, and that there were delays in the system due to sensing and information processing not accounted for in the accompanying theory, the results are very encouraging. For more details see also Joshua Marshall’s page .