Research Topics

The last decades have seen an increasing number of application domains where vehicles are required to visit "customers" that arrive dynamically in time, are spatially distributed over an environment, and possibly require some type of additional on-site service (provided either by the driver of the vehicle, or by the vehicle itself). Delivery services, emergency services and sensor networks are clear examples. The routing of the vehicles is often dynamic and time-constrained, in the sense that customers have (possibly stochastic) deadlines on their waiting times; moreover, the design of routing policies is affected by the mode of implementation (centralized or decentralized).

By embedding the problem within the framework of queueing theory, the main objective of this project is the design of scalable, robust, and adaptive vehicle routing policies with provable performance guarantees, and amenable to decentralized implementation. Specific questions that are addressed are: what is the minimum number of mobile vehicles needed to ensure that a desired fraction of customers receive service before they abandon the system due to impatience? What policy should the vehicles execute to ensure that this objective is attained?

The significance of this project stems from two facts: First, the structural insights that one obtains can provide the system designer with essential information to build business and strategic planning models regarding, e.g., fleet sizing and depot locations. Second, this analysis provides directions and guidelines to route the vehicles once the system is deployed.

Related publications:
-[J8]: presents adaptive and distributed policies for dynamic vehicle routing.
-[J4]: studies the case where demands have deterministic deadlines on their waiting times.
-[J7]: studies the case with multiple priority classes of service demands.

Other related publications: [C11], [C8], [C7], and [C6].

In the near future, large groups of autonomous robots will be used to perform complex tasks including transportation and distribution, logistics, surveillance, search and rescue operations, humanitarian demining, and environmental monitoring. The design of cooperative control policies for the robots has to typically address three key challenges: (i) task allocation among the robots, (ii) service scheduling for each robot, and (iii) design of loitering strategies, i.e., strategies to adopt for robots with no assigned tasks. In general, these challenges are coupled. Therefore, devising an optimal, or at least provably efficient policy is often a difficult problem.

A natural way to reduce the complexity is to partition the workspace among the robots and then let each robot follow a certain set of rules in its own region. To what extent does this decoupling strategy affect optimality? The first objective of this project is to find specific scenarios where one can retain optimality, or at least some degree of optimality, under this partitioning scheme.

Then, the second objective of the project is to design partitioning algorithms that do not require any centralized computation: in fact, this is a necessary property for robotic networks comprising several robots that operate in an unknown dynamic environment. The focus is on equitable partitioning policies, since they naturally lead to workload balancing. The design and analysis of such algorithms require a variety of techniques from control theory, computational geometry and algebraic topology.

Related publications:
-[J8]: discusses scenarios where partitioning policies are optimal.
-[J6]: presents provably correct and spatially-distributed algorithms for equitable partitions with special properties.
-[J5]: reviews several types of partitioning schemes.

Other related publications: [C12], [C9], and [C6].

Significant interest in formation flying started to develop in the late 1990s, and today formation flying is a critical technology for many planned and future missions of NASA, the DoD, and ESA. Broadly speaking, spacecraft formation algorithms can be divided into three main architectures: (i) Multiple-Input Multiple-Output (MIMO), in which the formation is treated as a single multiple-input, multiple-output plant, (ii) Leader/Follower, in which individual spacecraft controllers are connected hierarchically, and (iii) Cyclic, in which individual spacecraft controllers are connected non-hierarchically. By allowing non-hierarchical connections between individual spacecraft controllers, Cyclic algorithms can perform better than Leader/Follower algorithms, and can distribute control effort more evenly. Moreover, Cyclic algorithms are generally more robust than MIMO algorithms, for which a local failure can have a global effect. Finally, Cyclic algorithms can also be completely distributed in the sense that there is neither a coordinating agent nor instability resulting from single point failures. The two primary drawbacks of Cyclic algorithms are that the stability of these algorithms and their information requirements are poorly understood; in particular, the stability analysis of Cyclic algorithms is difficult since the cyclic structure introduces feedback paths (a comprehensive and up-to-date survey on spacecraft formation flying can be found here).

Motivated by the previous discussion, the objective of this project is to propose a class of Cyclic algorithms for formation flying, for which (i) a rigorous stability analysis is possible, and (ii) the information requirements are minimal. In particular, we study control policies that only rely on relative measurements, since in deep-space missions global measurements may not be available. On the 31st of October 2008, our control policies have been tested on the International Space Station. Specifically, we tested balanced circular formation for three Spheres satellites (videos of the tests can be found here).

Related publications:
-[J3]: presents a decentralized control policy for symmetric formations in multi-agent systems. It is shown that n agents, each one pursuing its leading neighbor along the line of sight rotated by a common offset angle alpha, eventually converge to a single point, a circle or a logarithmic spiral pattern, depending on the value of alpha.
-[J9]: studies cyclic-pursuit control laws for formation flight, for both single- and double-integrator models in three dimensions. These control laws are then extended to deal with the (linearized) relative dynamics of spacecraft, e.g., in the Earth's gravitational field.

Other related publications: [C5], and [C10].

Fully autonomous robots able to perform missions in harsh and hazardous environments are nowadays the Holy Grail in robotics research. Indeed, biology provides a wealth of inspiration: insects are able to transverse harsh terrains, to climb over obstacles, or even to walk upside down. Hence, the objective of this research is the design of a legged robot that imitates the mechanics and the behaviors of the insects, in particular of the cockroaches.

In order to replicate at least in part the extraordinary agility of cockroaches, the robot has six legs, and each of the three pairs of legs has a unique design: front legs and middle legs have 3 degree of freedoms and a kind of pantograph mechanism that facilitates the task of climbing obstacles, while the rear legs have 2 degrees of freedom and a piston-like design that guarantees powerful forward thrusting. The control system architecture has a two-level hierarchical organization: the low level control is based on a CNN-based Central Pattern Generator (CPG); the CPG provides the basic rhythmic signals needed for locomotion. On the other hand, the high level control is responsible for handling complex tasks like obstacle climbing and target pursuing, and is behavior-based. The key idea that we introduced is the formalization of a behavior as a Motor Map driven by an adaptive reward function.

The robot has been built in the robotics lab of the University of Catania, and its name is Gregor I, in homage to the writer F. Kafka. Experiments show that Gregor I is able to walk at the travel speed of 0.1 body length per second, and to successfully negotiate obstacles whose height is larger than the 120% of the height of the front part of the robot - a good results if compared to the performance of other hexapod robots.

In collaboration with S. De Fiore and S. Sorbello, I also designed and built the control system of a mobile robot, named M6, whose purpose is the exploration of volcanos. M6 has six wheels which are coupled to the chassis by means of revolute joints. Each wheel is independently actuated. The robot uses a peristaltic motion to negotiate steep slopes.

Related publications:
-[J2]: discusses the structure of Gregor I.
-[J1]: discusses the control architecture of Gregor I.
-[C3]: presents a general approach for the unsupervised learning of behaviors in a behavior-based robot.

Other related publications: [C1], [C2], and [C4].