30 giugno 2010
Mentre ancora tutto tace sul fronte ESA, un sacco di cose sembrano muoversi invece in quel di Plymouth. In primo luogo perche’ il paper che avevo sottomesso a suo tempo per TAROS 2010 e’ stato accettato, anche se soltanto per una poster presentation. Non ho di che lamentarmi dato che il paper non era obiettivamente di alta qualita’ e finira’ comunque sui proceedings. Adesso, entro un paio di settimane, dovro’ preparare la versione camera ready. In secondo luogo, un amico mi ha informato sul fatto che proprio nella ridente capitale del Devon si terra’ a breve una summer school interessante per chiunque si occupi di machine learning: ISSPR – International Summer School on Pattern Recognition. Infine, a tener ravvivata l’atmosfera e’ anche il mio supervisor che mi ha comunicato via mail come i lor signori americani che mi pagano il PhD siano disposti ad estendere la mia borsa per ulteriori sei mesi. A patto che si presenti loro un progetto relativo al lavoro da svolgere durante questi ulteriori sei mesi. Detto, fatto. Armato di carta e penna (o, meglio, Word e tastiera) oggi pomeriggio ho scritto il proposal. Nel caso potesse interessarmi, lo trovate qui sotto.
Flocking, defined as ‘the collective motion of a large number of self-propelled entities’  is a phenomena commonly observed in nature among birds and other animals (though it tends to be called in different ways according to the animals involved into it: swarming for insects, herding for quadrupeds, schooling for fish, etc.). Flocking behaviours are beneficial from both an individual and a group perspective. Among the most obvious advantages driving an individual to join a group of conspecifics we can mention the protection a flock (as well as a herd, or a school) offers against potential menaces (mostly predators, though someone may argue that being inside a flock increases the likelihood of being detected by a predator) , and the energy saving all the flock members can benefit from because of the less air resistance they will encounter during their flight . Some older studies, e.g. , also introduced the so-called ‘many wrongs’ principle, suggesting that flying inside a flock during long migrations could improve the navigation efficiency for all the individuals (more recently proven true in , assuming that the size of the flock is large enough). As demonstrated for example in , as well as in a number of researches carried out within the relatively new field of swarm robotics, robots also can benefit from the adoption of flocking principles when involved in a collective navigation task. These properties might turn particularly useful in aerial robotics, specifically in the domain of MUAVs (Micro-Unmanned Aerial Vehicles) . For this specific realm, the biggest advantages are two: energy saving (thus allowing for a longer flight duration) and easiness from a control point of view.
How a flock really works in nature is still unclear. An agreement has yet to be reached within the scientific community when it comes to answer some basic questions, as whether animal flocks rely on one or more ‘leaders’ (and the flock members just synchronise their movements with those of the leader) or the individuals must all be considered egalitarian peers that generate an overall flocking behaviour as the casual result emerging from the execution of a set of individually-motivated actions. Recent studies focused on pigeons homing behaviours  have demonstrated how these birds elect, from time to time, a different set of leaders to imitate in their navigation behaviours. The leaders tend to be those with the best skills in individual navigation. This view seems to be in contrast with the trend emerged from the research carried out in robotics/computer science, as well as in physics, during the last few decades. The studies on this field, heavily influenced by the pioneeristic work by Reynolds , have been looking at flocking behaviours as complex high-level phenomena emerging from the simple lower-level interactions among the single individuals composing the flock. This view is not necessarily incongruent with the fact of having a leader, but a common assumption in most of these works (see for example [10) is about all the flock/swarm members being on the same hierarchic level. To recognize that animals flocks indeed rely on the presence of individuals hierarchically higher than others opens the road for a all new set of models that can be built in order to improve our understanding of flocking behaviours.
Experiments on group behaviours are common in the literature about ground-based robots (see among others  and ), but still in their infancy for what concerns aerial robotics. One of the very few application of flocking principles on physical flying robots consists in the work described in , with some testing performed on real blimps, though focused on a ‘particular’ topic, which is the so-called secondary swarming.
The project we propose herein aims to further improve the results recently obtained through an innovative approach by Ruini et al. , who have recently been able to design and successfully test on real MUAVs an intelligent flocking algorithm. The work will be carried out in simulation, using the same computer model developed by Ruini for the original work. The simulator – written on C++ and relying on multi-platform open-source libraries – is based upon the senseFly’s swinglet MUAV , a lightweight fixed-wing aircraft characterised by an 80 cm wingspan, an overall weight of less than 500 g, and propelled by an electric motor which allows the robot to fly at [30;50] km/h for up to 60 minutes.
Among the number of aspects that could potentially be tackled using the software simulator, the project will mainly focus on two aspects:
- implementation of a (neuro)evolutionary approach in order to improve some aspects of the previously developed flocking algorithm;
- identification of new metrics for the evaluation of the flocking behaviour.
The flocking algorithm can potentially be improved in many different ways, making it more plausible from a biological point of view and, at the same time, more efficient performance-wise. In , for example, the MUAVs members of a certain team share among them information about their absolute position using explicit communication (through a wireless data link). This information is used to compute various statistics (i.e., the average heading of the flock, the centre of mass, etc.), employed in turn to determine the course of action to undertake. A neural network-based controller can be trained or evolved in order to extract the same information based on local readings (following the approach outlined in , where swarming is obtained without the use of positioning information), thus reducing the need for exchanging information and performing complex mathematical calculations not particularly plausible from a biological perspective.
Another interesting potential improvement consists in optimising (through evolutionary methodologies) the manoeuvres that implement the flocking behaviour. In , aspects as heading alignment, velocity matching, and convergence toward the centre of the flock are all algorithmically managed. The proposed solutions for each of these problems have demonstrated to be working, but they are not necessarily the most optimised ones. Better solutions can be identified relying on artificial evolution.
At the same time, identifying an appropriate set of metrics for evaluating flocking behaviours (since those found across the literature tends to be not of general usage, but rather specific for the purposes of the single studies) could help to identify other areas for potential improvements, as well as provide the entire field with a general purpose valuable contribute.
The project might also involve collaboration with the Laboratory of Intelligent Systems (LIS) at the Ecole Polytechnique Federale de Lausanne (EPFL), Switzerland. Relying on the fleet of MUAVs available there the investigator could potentially spend a few weeks in Lausanne testing on physical robotics platforms the controllers developed in simulation.
 O’Loan, O.J., and Evans, M.R. (1999). Alternating steady state in one-dimensional flocking. Journal of Physics A: Math. Gen., vol. 32(8), pp. L99-L105.
 Lebar Bajec, I., and Heppner, F.H. (2009). Organized flight in birds. Animal Behaviour, vol. 78(4), pp. 777-789.
 Weimerskirch, H., Martin, J., Clerquin, Y., Alexandre, P., and Jiraskova, S. (2001). Energy saving in flight formation. Nature, vol. 413, pp. 697-698.
 Bergman, G., and Donner, K. (1964). An analysis of the spring migration of the common scoter and the long-tailed duck in southern Finland. Acta Zoologica Fennica, vol. 105, pp. 1-59.
 Simons, A.M. (2004). Many wrongs: the advantage of group navigation. Trends in Ecology and Evolution, vol. 19(9), pp. 453-455.
 Gokce, F., and Sahin, E. (2010). The pros and cons of flocking in the long-range “migration” of mobile robot swarms. Theoretical Computer Science, vol. 411(21), pp. 2140-2154.
 Sullivan, J.M. (2006). Revolution or evolution? The rise of the UAVs. IEEE Technology and Society Magazine, vol. 25(3), pp. 43-49.
 Nagy, M., Akos, Z., Biro, D., and Vicsek, T. (2010). Hierarchical group dynamics in pigeon flocks. Nature, vol. 464(7290), pp. 890-893.
 Reynolds, C.W. (1987). Flocks, herds, and schools: a distributed behavioral model. In Proceedings of ACM SIGGRAPH ’87, vol. 21(4), pp. 25-34.
 Baldassarre, G., Parisi, D., and Nolfi, S. (2006). Distributed coordination of simulated robots based on self-organization. Artificial Life, vol. 12(3), pp. 289-311.
 Moeslinger, C., Schmickl, T., and Crailsheim, K. (2009). A minimalist flocking algorithm for swarm robots. Proceedings of ECAL’09, 10th European Conference on Artificial Life.
 Turgut, A.E., Celikkanat, H., Gokce, F., and Sahin, E. (2008). Self-organized flocking in mobile robot swarms. Swarm Intelligence, vol. 2, pp. 97-120.
 Melhuish, C., Welsby, J., and Greenway, P. (2002). Gradient ascent with a group of minimalist real robots: implementing secondary swarming. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, vol. 2, pp. 509-514.
 Ruini, F., Hauert, S., Leven, S., Zufferey, J.-C., Cangelosi, A., and Floreano, D. (in preparation). A bio-inspired flocking algorithm for MUAVs. Experiments in computer simulations and on real robots.
 Leven, S., Zufferey, J.-C., and Floreano, D. (2009). A minimalist control strategy for small UAVs. In Proceedings of IROS 2009, the IEEE/RSJ International Conference on Intelligent RObots and Systems, pp. 2873-2878.
 Hauert, S., Zufferey, J.-C., and Floreano, D. (2009). Evolved swarming without positioning information: an application in aerial communication relay. Autonomous Robots, vol. 26(1), pp. 21-32.