Design of control software can be classified along four axes:
Automatic design is justified when any of the following conditions hold:
The third condition is the one Chapter 3 flagged: in Chapter 3 the mission was defined as explicitly sampled from a class — the class is the niche, written down. Here the same idea does the economic work: if every mission is different, designing each one by hand is unaffordable, and the design method itself becomes the product.
The lecture gives the methodology in four steps:
In the manifest, the problem is stated more precisely: the design problem is cast into an optimization problem that is solved off-line — before the swarm is deployed in the target environment. An optimization algorithm searches a space of possible designs with the goal of maximising an appropriate mission-specific performance measure; the performance of candidate designs is assessed via computer-based simulations; once the optimization terminates, the selected design is uploaded to the robots.
| Issue | What it is |
|---|---|
| Training and test sets | Candidate designs are tuned on a sample of missions; performance must then be assessed on missions not used for tuning — the machine-learning validation distinction of Chapter 15 |
| Merit factor | The objective function (or fitness function) that measures how good a design is; it must quantitatively capture the criteria that matter |
| Simulation | The physics-based model used to evaluate candidate designs without touching real robots — cheap, fast, repeatable, but approximate |
| Reality gap | The possibly subtle but inevitable difference between the model and the real system (Brooks 1992; Jakobi et al. 1995) — the most challenging issue in off-line design |
Any automatic design study you read (or write) can be graded against these four: Were the missions used for training different from those used for testing? Is the merit factor stated, and does it capture what the user actually wants? Is the simulation described well enough to be reproduced? Is the reality gap assessed by running real robots? The manifesto's guidelines (section 11) are exactly this checklist, made into research norms.
Examples named by the lecture, besides evolutionary robotics: AutoMoDe, Boolean network robotics, and online adaptation of nanowire networks — the last two reappear in Chapter 16 as the "hard case" of Chapter 3: adaptation that must happen during operation, on a substrate that cannot be reprogrammed.
AutoMoDe (Francesca et al., 2014) is an approach in which control software for robot swarms is automatically designed in the form of a probabilistic finite state machine (PFSM), by combining and fine-tuning preexisting parametric modules. The key idea: do not let the search invent the controller from nothing; give it a vocabulary of well-understood behaviours and let it decide which to combine and how to tune them.
The design problem in swarms is the one Chapter 9 left open: requirements are naturally expressed at the collective level, but the designer must eventually define what each individual robot does; no general approach exists to derive individual behaviour from desired collective behaviour, so manual design proceeds by trial and error and completely relies on the intuition and skill of the designer. Automatic design casts the problem into an optimization problem: the solution space comprises instances of control software that conform to a predefined parametric architecture, and an optimization algorithm searches it — which amounts to tuning the free parameters of the architecture.
AutoMoDe-Vanilla is a first method that complies with the AutoMoDe approach, specialised for a version of the e-puck robot. In Vanilla, twelve modules are available for assembly into a probabilistic finite state machine: six behaviours — exploration, stop, phototaxis, anti-phototaxis, attraction, repulsion (all but stop include an obstacle avoidance mechanism) — and six transitions — black-floor, gray-floor, white-floor, neighbour-count, inverted-neighbour-count, fixed-probability. The search space is the space of PFSMs comprising up to four states and up to four outgoing edges from each state.
In Study A, Vanilla and EvoStick (a design method that uses an evolutionary algorithm to optimize a neural network) are compared with human designers on five swarm robotics tasks — different from those on which Vanilla and EvoStick were previously tested. The tasks were defined by researchers who, at the moment of defining them, were neither aware of the functioning of the two methods nor informed on which design methods were included in the study: the definition of the tasks was neutral, granting no a priori advantage to any method. The versions of Vanilla and EvoStick were exactly those of the original paper, with no modification to adapt them to the new tasks.
Two manual design methods complete the comparison:
Results of Study A:
Since Vanilla and C-Human operate on the same set of modules, the performance gap cannot be blamed on the architecture. The difference is to be ascribed to the mechanism adopted to combine and fine-tune the modules: the optimization algorithm. The study is a controlled experiment: same design space, different search engines, and the search engine lost. The fix is therefore to change the search engine — which is exactly what Chocolate does.
AutoMoDe-Chocolate differs from Vanilla in a single aspect: the optimization algorithm used to explore the design space. Vanilla adopts F-Race (with the default parameters of the irace package); Chocolate adopts Iterated F-Race — a more effective instance of the same racing family, which repeatedly runs races and uses the results to bias the sampling of new candidate configurations toward promising regions.
In Study B, the working hypotheses were: (i) by adopting a more advanced optimization algorithm, Chocolate improves over Vanilla; and (ii) the improvement is such that, under the experimental conditions considered, Chocolate outperforms C-Human. Both hypotheses were confirmed. The empirical campaign is unprecedented in the domain: 350 runs with a swarm of 20 robots, five methods tested on five tasks. Chocolate is the first automatic design method for robot swarms that, at least under specific experimental conditions, is shown to outperform a human designer.
Notice what the result does not say: the conditions are specific, the tasks belong to a class, and the humans were constrained by the same module vocabulary in the decisive comparison. The claim is a controlled, quantitative one — and the experimental protocol itself (neutral task definition, no task-specific modification, multiple tasks, multiple methods under the same conditions) is a contribution that Chapter 15 will generalise into a methodology.
The engine behind AutoMoDe is algorithm configuration: a metaheuristic is a general algorithmic template whose components need to be instantiated and properly tuned to yield a fully functioning algorithm; an instantiation is a configuration, and the configuration problem is the problem of selecting the optimal one. Birattari, Stützle, Paquete and Varrentrapp (2002) formalised it: given the finite set of candidate configurations Θ, the possibly infinite set of instances I with an unknown probability measure PI, the computation time t(i) allocated to each instance, and the random cost c(θ, i) of the best solution found by running θ on i for t(i) seconds, the problem is to find
θ* = arg min C(θ) with C(θ) = E[ c(θ, i) ]where the expectation is taken over both the instance distribution and the stochasticity of the run. The measures are not explicitly available, so the integrals are estimated in a Monte Carlo fashion on a training set of instances — the problem is one of generalisation, exactly as in machine learning.
The naive brute-force approach — run every candidate on a large fixed set of instances — wastes computation on bad candidates. A racing method instead evaluates the candidate configurations iteratively on new sampled instances and discards bad ones as soon as statistically sufficient evidence is gathered against them, so that computation concentrates on the promising ones. The lecture's summary:
Given all candidate configurations θ1, θ2, ..., θm, run them iteratively on new sampled problem instances and progressively discard the configurations that are statistically significantly worse; this way we do not waste computational time testing bad configurations. The R implementation is the irace package. Iterated F-Race (used by Chocolate) goes further: it runs several races, and each race uses the results of the previous ones to sample new candidate configurations in the most promising regions of the design space. A related family member named in the slides: CMA-ES (Covariance Matrix Adaptation Evolution Strategy), where parameters are variables of an optimization problem whose objective function is the performance of the resulting control program, and the variables are iteratively sampled according to a distribution adapted on the basis of the most promising previous samples.
Ten candidate configurations with hidden true means. Each "instance" gives every surviving candidate a noisy observation. As soon as a candidate's observations are statistically worse than the current best (a simplified pairwise criterion), it is eliminated. Watch computation concentrate on the leaders.
Birattari, Ligot, Bozhinoski, Brambilla, Francesca, Garattoni, Garzón Ramos, Hasselmann, Kegeleirs, Kuckling, Pagnozzi, Roli, Salman and Stützle (2019) wrote the manifesto of the automatic off-line design of robot swarms — the reference that frames this whole chapter. Its core definitions:
The assumption that missions are sampled according to a probability measure gives a formal meaning to the notion of expected performance and to any other statistics describing the aggregate behaviour of a design method across the missions of interest.
With few exceptions, existing methods were studied following protocols not conceived to address the core research questions: focus on a single mission; the design method is not the protagonist of the study and is not given a name; no comparison with alternatives; control software tested only in simulation with no assessment of the reality gap; and the frequent presence of an iterative human-in-the-loop process (run, inspect, modify the objective function, rerun) that is never reported in the article and cannot be repeated — so robustness and repeatability are not assessed.
The manifesto illustrates the approach with a running example. Fiorella owns a robot-swarm gardening business in the Brussels area, offering individually tailored service: every day she visits three or four customers with her swarm. Customers book via a form, asking for interventions (cutting grass, watering flowers...) and providing information on their garden (size, shape, orientation). The interventions and garden characteristics specify the mission; since the list of possible interventions and characteristics is huge, the class of possible missions is overwhelmingly large and diverse.
Fiorella relies on an automatic off-line method that designs and fine-tunes the behaviours of her swarm specifically for each mission — while she drives to the customer's garden, her powerful computers run simulations using the customer's information. The design must complete within the time of the ride: as she arrives, the selected design is uploaded and the swarm deployed. No per-mission human intervention and no test on the robots before deployment — both would increase costs dramatically.
First, it makes the class of missions concrete: the form, the gardens and the interventions define a distribution, and expected performance is defined over it. Second, it fixes the economic condition for automatic design: the investment in the method pays off only if design is repeated many times. Third, it makes the no-intervention constraint vivid: the design process runs while Fiorella drives, with no opportunity to inspect or adjust — the only condition for the process to qualify as automatic off-line design is that initial (partial) solutions are selected without per-mission human intervention and without recourse to tests in the target environment.
The manifesto closes with the tenets and guidelines for a healthy development of the domain. The two tenets: (i) automatic off-line design methods should not be mission-specific and should address a whole class of missions without modification; (ii) once a mission is specified, human intervention is not provided for in any phase of the design process. Researchers should therefore:
The vision: in a relatively close future, automatic off-line design will be a practically relevant way of realising robot swarms — likely not the only one (manual, semi-automatic, automatic on-line and hybrid approaches will keep their roles), but a major one. The long-term horizon is the DEMIURGE project (Chapter 9): an intelligent system able to design and realise robot swarms in a totally integrated and automatic way — hardware and control software — starting from requirements expressed in an appropriate specification language.
Chapter 9 ended with the design problem: requirements live at the collective level, the designer must decide the individual behaviour, and no general derivation exists. This chapter is the answer: cast design into optimization (FSA optimisation being one instance), search with racing, validate statistically (Chapter 15), and let the swarm itself be evaluated as a whole. Evolutionary robotics (Chapter 10) supplies the search machinery; automatic design supplies the framing. The two meet in DEMIURGE — and the "no best controller" lesson of Chapter 4 is what makes the whole enterprise compulsory rather than optional.
Axes: manual / semi-automatic / automatic; off-line / on-line; simulation / real robots; software / hardware / both. Automatic design is justified when: manual or semi-automatic techniques are not effective, efficient or too costly; the design has to be repeated many times; the mission cannot be precisely defined because it is sampled from a distribution; the designer wants to explore new solutions.
The robot program is represented in a formal language (e.g. FSM); the design problem is encoded into a learning problem; in the training phase an optimization algorithm is used (e.g. evolutionary techniques); the program is designed in simulation and then tested in a real setting. The design problem is cast into an optimization problem solved off-line, before deployment, maximising a mission-specific performance measure assessed via simulations.
Training and test sets (tuning vs assessment on different missions); merit factor (the objective/fitness function capturing the criteria that matter); simulation (the model used to evaluate candidates); reality gap (the difference between simulation models and reality — among the most challenging issues in automatic off-line design).
AutoMoDe is an approach in which control software for robot swarms is automatically designed in the form of a probabilistic finite state machine by combining and fine-tuning preexisting parametric modules. Vanilla specialises it for the e-puck: twelve modules — six behaviours (exploration, stop, phototaxis, anti-phototaxis, attraction, repulsion; all but stop include obstacle avoidance) and six transitions (black-floor, gray-floor, white-floor, neighbour-count, inverted-neighbour-count, fixed-probability). The search space comprises PFSMs with up to four states and four outgoing edges per state.
Vanilla and EvoStick (evolutionary neural-network design) were compared with human designers (U-Human, unconstrained; C-Human, constrained to the same modules as Vanilla) on five tasks defined neutrally by researchers unaware of the methods. Results: Vanilla outperforms EvoStick; Vanilla outperforms U-Human; Vanilla performs worse than C-Human. Since Vanilla and C-Human share the module vocabulary, the difference is ascribed to the optimization algorithm.
Chocolate differs from Vanilla in a single aspect: it adopts Iterated F-Race instead of F-Race to explore the design space. Study B confirmed both working hypotheses: the more effective optimization algorithm improves over Vanilla, and under the experimental conditions considered Chocolate outperforms C-Human — making it the first automatic design method for robot swarms shown to outperform a human designer (350 runs, swarm of 20 robots, five methods on five tasks).
Θ is the finite set of candidate configurations; I the set of instances with probability measure PI; t(i) the computation time allocated to instance i; c(θ,i) the random cost of the best solution found by running θ on i for t(i) seconds. The problem is θ* = arg min C(θ) with C(θ) = E[c(θ,i)], the expectation over both instance distribution and run stochasticity, estimated on a training set of instances — a problem of generalisation, as in machine learning.
A racing method evaluates candidate configurations iteratively on new sampled instances and discards bad ones as soon as statistically sufficient evidence is gathered against them, so computation is not wasted on bad configurations. F-Race is the basic procedure; Iterated F-Race (adopted by Chocolate, via the irace R package) performs several races and uses the results of previous races to sample new candidates in the most promising regions of the design space. CMA-ES is a related approach that adapts a sampling distribution to the most promising previous samples.
The design problem is cast into an optimization problem solved off-line, before deployment: an optimization algorithm searches a space of possible designs to maximise a mission-specific performance measure, assessed via simulations; the selected design is then uploaded and deployed, crossing the reality gap. The method must operate on missions sampled from a class of interest without mission-specific adjustments or per-mission human intervention. The class of missions — a set of missions with a probability measure — gives formal meaning to expected performance.
Fiorella runs a robot-swarm gardening business; customers specify interventions and garden characteristics, defining a mission sampled from a huge class. While she drives to the customer, her computers automatically design and fine-tune the swarm's behaviour for that specific mission; on arrival the design is uploaded and deployed, with no per-mission human intervention or testing. The example illustrates the class-of-missions notion, the economic condition (design repeated many times), and the no-intervention constraint that qualifies a process as automatic off-line design.
(1) Clear and thorough description of methods including all parameter values; (2) precise characterisation of the platforms; (3) identify and name methods; (4) publish implementations; (5) test on multiple missions; (6) identify the class of missions addressed; (7) comparative studies under the same conditions; (8) robot experiments to assess robustness to the reality gap.
ER is the historical core of automatic design: it optimises robots by evolution. Automatic design generalises it: the design problem is cast into an optimization problem over a parametric controller architecture, and any optimization algorithm can be used — evolutionary techniques are one option, FSA optimisation, behaviour-tree configuration and Boolean networks are others. The same design problem (collective requirements, individual behaviour) is attacked; the search machinery differs.