A Draft Open Standard for an Ethical Black Box

About 5 years ago we proposed that all robots should be fitted with the robot equivalent of an aircraft Flight Data Recorder to continuously record sensor and relevant internal status data. We call this an ethical black box (EBB). We argued that an ethical black box will play a key role in the processes of discovering why and how a robot caused an accident, and thus an essential part of establishing accountability and responsibility.

Since then, within the RoboTIPS project, we have developed and tested several model EBBs, including one for an e-puck robot that I wrote about in this blog, and another for the MIRO robot. With some experience under our belts, we have now drafted an Open Standard for the EBB for social robots - initially as a paper submitted to the International Conference on Robots Ethics and Standards. Let me now explain first why we need a standard, and second why it should be an open standard.

Why do we need a standard specification for an EBB? As we outline in our new paper, there are four reasons:

1. A standard approach to EBB implementation in social robots will greatly benefit accident and incident (near miss) investigations. 
2. An EBB will provide social robot designers and operators with data on robot use that can support both debugging and functional improvements to the robot. 
3. An EBB can be used to support robot ‘explainability’ functions to allow, for instance, the robot to answer ‘Why did you just do that?’ questions from its user. And,
4. a standard allows EBB implementations to be readily shared and adapted for different robots and, we hope, encourage manufacturers to develop and market general purpose robot EBBs.

And why should it be an Open Standard? Bruce Perens, author of The Open Source Definition, outlines a number of criteria an open standard must satisfy, including:

• “Availability: Open standards are available for all to read and implement.
  
• Maximize End-User Choice: Open Standards create a fair, competitive market for implementations of the standard.
• No Royalty: Open standards are free for all to implement, with no royalty or fee.
• No Discrimination: Open standards and the organizations that administer them do not favor one implementor over another for any reason other than the technical standards compliance of a vendor’s implementation.
• Extension or Subset: Implementations of open standards may be extended, or offered in subset form.”

These are *good* reasons.

The most famous and undoubtedly the most impactful Open Standards are those that specified Internet protocols, such as FTP and email. They were, and still are, called Requests for Comments (RFCs) to reflect the fact that they were - especially in the early years - drafts for revision. As a mark of respect we also regard our draft 0.1 Open Standard for an EBB for Social Robots, as an RFC. You can find draft 0.1 in Annex A of the paper on arXiv here.

Not only is this a first draft, it is also incomplete, covering only the specification of the data and its format, that should be saved in an EBB for social robots. Given that the EBB data specification is at the heart of the EBB standard, we feel that this is sufficient to be opened up for comments and feedback. We will continue to extend the specification, with subsequent versions also published on arXiv.

Please feel free to either submit comments to this blog post (best because everyone can see the comments), or by contacting me directly via email. All constructive comments that result in revisions to the standard will be acknowledged in the standard.

Back to Robot Coding part 3: testing the EBB

In part 2 a few weeks ago I outlined a Python implementation of the ethical black box. I described the key data structure - a dictionary which serves as both specification for the type of robot, and the data structure used to deliver live data to the EBB. I also mentioned the other key robot specific code: 

# Get data from the robot and store it in data structure spec

def getRobotData(spec):

Having reached this point I needed a robot - and a way of communicating with it - so that I could both write getRobotData(spec) and test the EBB. But how to do this? I'm working from home during lockdown, and my e-puck robots are all in the lab. Then I remembered that the excellent robot simulator V-REP (now called CoppeliaSim) has a pretty good e-puck model and some nice demo scenes. V-REP also offers multiple ways of communicating between simulated robots and external programs (see here). One of them - TCP/IP sockets - appeals to me as I've written sockets code many times, for both real-world and research applications.  Then a stroke of luck: I found that a team at Ensta-Bretagne had written a simple demo which shows how to connect a Python program to a robot in V-REP, using sockets. So, first I got that demo running and figured out how it works, then used the same approach for a simulated e-puck and the EBB. Here is a video capture of the working demo.

So, what's going on in the demo? The visible simulation views in the V-REP window show an e-puck robot following a black line which is blocked by both a potted plant and an obstacle constructed from 3 cylinders. The robot has two behaviours: line following and wall following. The EBB requests data from the e-puck robot once per second, and you can see those data in the Python shell window. Reading from left to right you will see first the EBB date and time stamp, then robot time botT, then the 3 line following sensors lfSe, followed by the 8 infra red proximity sensors irSe. The final two fields show the joint (i.e. wheel) angles jntA, in degrees, then the motor commands jntD. By watching these values as the robot follows its line and negotiates the two obstacles you can see how the line and infra red sensor values change, resulting in updated motor commands.

Here is the code - which is custom written both for this robot and the means of communicating with it - for requesting data from the robot.

# Get data from the robot and store it in spec[]

# while returning one of the following result codes

ROBOT_DATA_OK = 0

CANNOT_CONNECT = 1

SOCKET_ERROR = 2

BAD_DATA = 3

def getRobotData(spec):

    # This function connects, via TCP/IP to an ePuck robot in V-REP

    # create a TCP/IP socket and connect it to the simulated robot

    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

    try:

        sock.connect(server_address_port)

    except:

        return CANNOT_CONNECT

    sock.settimeout(0.1) # set connection timeout

    

    # pack a dummy packet that will provoke data in response

    #   this is, in effect, a 'ping' to ask for a data record

    strSend = struct.pack('fff',1.0,1.0,1.0)

    sock.sendall(strSend) # and send it to V-REP

    # wait for data back from V-REP

    #   expect a packet with 1 time, 2 joints, 2 motors,   

    #   3 line sensors and 8 irSensors. All floats because V-REP

    #   total packet size = 16 x 4 = 64 bytes

    data = b''

    nch_rx = 64 # expect this many bytes from  V-REP 

    try:

        while len(data) < nch_rx:

            data += sock.recv(nch_rx)

    except:

        sock.close()

        return SOCKET_ERROR

    # unpack the received data

    if len(data) == nch_rx:

        # V-REP packs and unpacks in floats only so...

        vrx = struct.unpack('ffffffffffffffff',data)

        # now move data from vrx[] into spec[], while rounding floats

        spec["botTime"] = [ round(vrx[0],2) ] 

        spec["jntDemands"] = [ round(vrx[1],2), round(vrx[2],2) ]

        spec["jntAngles"] = [ round(vrx[3]*180.0/math.pi,2)

                              round(vrx[4]*180.0/math.pi,2) ]

        spec["lfSensors"] = [ round(vrx[5],2), 

                              round(vrx[6],2), round(vrx[7],2) ]

        for i in range(8):

            spec["irSensors"][i] = round(vrx[8+i],3)       

        result = ROBOT_DATA_OK

    else:       

        result = BAD_DATA

    sock.close()

    return result

The structure of this function is very simple: first create a socket then open it, then make a dummy packet and send it to V-REP to request EBB data from the robot. Then, when a data packet arrives, unpack it into spec, then close the socket before returning. The most complex part of the code is data wrangling.

Would a real EBB collect data in this way? Well if the EBB is embedded in the robot then probably not. Communication between the robot controller and the EBB might be via ROS messages, or even more directly, by - for instance - allowing the EBB code to access a shared memory space which contains the robot's sensor inputs, command outputs and decisions. But an external EBB, either running on a local server or in the cloud, would most likely use TCP/IP to communicate with the robot, so getRobotData() would look very much like the example here. 

The Pedestrian Experiment

Followers of this blog will know that I have been working for some years on simulation-based internal models - demonstrating their potential for ethical robots, safer robots and imitating robots. But pretty much all of our experiments so far have involved only one robot with a simulation-based internal model while the other robots it interacts with have no internal model at all.

But some time ago we wondered what would happen if two robots, each with a simulation-based internal model, interacted with each other. Imagine two such robots approaching each other in the same way that two pedestrians approach each other on the sidewalk. Is it possible that these 'pedestrian' robots might, from time to time, engage in the kind of 'dance' that human pedestrians do when one steps to their left and the other to their right only to compound the problem of avoiding a collision with a stranger? The answer, it turns out, is yes!

The idea was taken up by Mathias Schmerling at the Humboldt University of Berlin, adapting the code developed by Christian Blum for the Corridor experiment. Chen Yang, one of my masters students, has now updated Mathias' code and has produced some very nice new results.

Most of the time the pedestrian robots pass each other without fuss but in something between 1 in 5 and 1 in 10 trials we do indeed see an interesting dance. Here are a couple of examples of the majority of trials, when the robots pass each other normally, showing the robots' trajectories. In each trial blue starts from the left and green from the right. Note that there is an element of randomness in the initial directions of each robot (which almost certainly explains the relative occurrence of normal and dance behaviours).

And here is a gif animation showing what's going on in a normal trial. The faint straight lines from each robot show the target directions for each next possible action modelled in each robot's simulation-based internal model (consequence engine); the various dotted lines show the predicted paths (and possible collisions) and the solid blue and green lines show which next action is actually selected following the internal modelling.

Here is a beautiful example of a 'dance', again showing the robot trajectories. Note that the impasse resolves itself after awhile. We're still trying to figure out exactly what mechanism enables this resolution.

And here is the gif animation of the same trial:

Notice that the impasse is not resolved until the fifth turns of each robot.

Is this the first time that pedestrians passing each other - and in particular the occasional dance that ensues - has been computationally modelled?

All of the results above were obtained in simulation (yes there really are simulations within a simulation going on here), but within the past week Chen Yang has got this experiment working with real e-puck robots. Videos will follow shortly.

---

Acknowledgements.

I am indebted to the brilliant experimental work of first Christian Blum (supported by Wenguo Liu), then Mathias Schmerling who adapted Christian's code for this experiment, and now Chen Yang who has developed the code further and obtained these results.

Simulation-based internal models for safer robots

Readers of this blog will know that I've become very excited by the potential of robots with simulation-based internal models in recent years. So far we've demonstrated their potential in simple ethical robots and as the basis for rational imitation. Our most recent publication instead examines the potential of robots with simulation-based internal models for safety. Of course it's not hard to see why the ability to model and predict the consequences of both your own and others' actions can help you to navigate the world more safely than without that ability.

Our paper Simulation-Based Internal Models for Safer Robots demonstrates the value of anticipation in what we call the corridor experiment. Here a smart robot (equipped with a simulation based internal model which we call a consequence engine) must navigate to the end of a corridor while maintaining a safe space around it at all times despite five other robots moving randomly in the corridor - in much the same way you and I might have to navigate down a busy office corridor while others are coming in the opposite direction.

Here is the abstract from our paper:

In this paper, we explore the potential of mobile robots with simulation-based internal models for safety in highly dynamic environments. We propose a robot with a simulation of itself, other dynamic actors and its environment, inside itself. Operating in real time, this simulation-based internal model is able to look ahead and predict the consequences of both the robot’s own actions and those of the other dynamic actors in its vicinity. Hence, the robot continuously modifies its own actions in order to actively maintain its own safety while also achieving its goal. Inspired by the problem of how mobile robots could move quickly and safely through crowds of moving humans, we present experimental results which compare the performance of our internal simulation-based controller with a purely reactive approach as a proof-of-concept study for the practical use of simulation-based internal models.

So, does it work? Thanks to some brilliant experimental work by Christian Blum the answer is a resounding yes. The best way to understand what's going on is with this wonderful gif animation of one experimental run below. The smart robot (blue) starts at the left and has the goal of safely reaching the right hand end of the corridor – its actual path is also shown in blue. Meanwhile 5 (red) robots are moving randomly (including bouncing off walls) and their actual paths are also shown in red; these robots are equipped only with simple obstacle avoidance behaviours. The larger blue circle shows blue's 'attention radius' – to reduce computational effort blue will only model red robots within this radius. The yellow paths in front of the red robots in blue's attention radius show blue's predictions of how those robots will move (taking into account collisions with the corridor walls and with blue and each other). The light blue projection in front of blue shows which of the 34 next possible actions of blue that is internally modelled is actually chosen as the next action (which, as you will see, sometimes includes standing still).

What do the results show us? Christian ran lots of trials – 88 simulations and 54 real robot experiments – over four experiments: (1) the baseline in simulation – in which the blue robot has only a simple reactive collision avoidance behaviour, (2) the baseline with real robots, (3) using the consequence engine (CE) in the blue robot in simulation, and (4) using the consequence engine in the blue robot with real robots. In the results below (a) shows the time taken for the blue robot to reach the end of the corridor, (b) shows the distance that the blue robot covers while reaching the end of the corridor, (c) shows the “danger ratio” experienced by the blue robot, and (d) shows the number of consequence engine runs per timestep in the blue robot. The danger ratio is the percentage of the run time that anther robot is within the blue robot’s safety radius.

For a relatively small cost in additional run time and distance covered, panels (a) and (b), the danger ratio is very significantly reduced from a mean value of ~20% to a mean value of zero, panel (c). Of course there is a computational cost, and this is reflected in panel (d); the baseline experiment has no consequence engine and hence runs no simulations, whereas the smart robot runs an average of between 8 and 10 simulations per time-step. This is exactly what we would expect: predicting the future clearly incurs a computational overhead.

---

Full paper reference:

Blum C, Winfield AFT and Hafner VV (2018) Simulation-Based Internal Models for Safer Robots. Front. Robot. AI 4:74. doi: 10.3389/frobt.2017.00074

Acknowledgements:
I am indebted to Christian Blum who programmed the robots, set up the experiment and obtained the results outlined here. Christian lead authored the paper, which was also co-authored by my friend and research collaborator Verena Hafner, who was Christian's PhD advisor.

Forgetting may be important to cultural evolution

Our latest paper from the Artificial Culture project has just been published: On the Evolution of Behaviors through Embodied Imitation.

Here is the abstract

This article describes research in which embodied imitation and behavioral adaptation are investigated in collective robotics. We model social learning in artificial agents with real robots. The robots are able to observe and learn each others' movement patterns using their on-board sensors only, so that imitation is embodied. We show that the variations that arise from embodiment allow certain behaviors that are better adapted to the process of imitation to emerge and evolve during multiple cycles of imitation. As these behaviors are more robust to uncertainties in the real robots' sensors and actuators, they can be learned by other members of the collective with higher fidelity. Three different types of learned-behavior memory have been experimentally tested to investigate the effect of memory capacity on the evolution of movement patterns, and results show that as the movement patterns evolve through multiple cycles of imitation, selection, and variation, the robots are able to, in a sense, agree on the structure of the behaviors that are imitated.

Let me explain.

In the artificial culture project we implemented social learning in a group of robots. Robots were programmed to learn from each other, by imitation. Imitation was strictly embodied, so robots observed each other using their onboard sensors and, on the basis of only visual sense data from a robot’s own camera and perspective, the learner robot inferred another robot’s physical behaviour. (Here is a quick 5 minute intro to the project.)

Not surprisingly embodied robot-robot imitation is imperfect. A combination of factors including the robots’ relatively low-resolution onboard camera, variations in lighting, small differences between robots, multiple robots sometimes appearing within a learner robot’s field of view, and of course having to infer a robot’s movements by tracking the relative size and position of that robot in the learner’s field of view, lead to imitation errors. And some movement patterns are easier to imitate than others (think of how much easier it is to learn the steps of a slow waltz than the samba by watching your dance teacher). The fidelity of embodied imitation for robots, just as for animals, is a complex function of four factors: (1) the behaviours being learned, (2) the robots’ sensorium and morphology, (3) environmental noise and (4) the inferential learning algorithm.

But rather than being a problem, noisy social learning was our aim. We are interested in the dynamics of social learning, and in particular the way that behaviours evolve as they propagate through the group. Noisy social learning means that behaviours are subject to variation as they are copied from one robot to another. Multiple cycles of imitation (robot B learns behaviour m from A, then robot C learns the same behaviour m′ (m mutated), from robot B, and so on), gives rise to behavioural heredity. And if robots are able to select which learned behaviours to enact we have the three Darwinian operators for evolution, except that this is behavioural, or memetic, evolution.

These experiments show that embodied behavioural evolution really does take place. If selection is random, that is robots select which behaviour to enact from those already learned – with equal probability, then we see several interesting findings.

1. If by chance one or more high fidelity copies follow a poor fidelity imitation, the large variation in the initial noisy learning can lead to a new behavioural species, or traditions. Thus showing that noisy social learning can play a role in the emergence of novelty in behavioural (i.e. cultural) evolution. That was written up in Winfield and Erbas, 2011.

But it is the second and third findings that we describe in our new paper.

2. We see that behaviours appear to adapt to be easier to learn, i.e. better ‘fitted’ to the robot swarm. The way to think about this is that the robots' sensors and bodies, and physical environment of the arena with several robots (including lighting), together comprise the 'ecological niche' for behavioural evolution. Behaviours mutate but the ones better fitted to that niche survive.

3. The third finding from this series of experiments is perhaps the most unexpected and the one I want to outline in a bit more detail here. We ran the same embodied behavioural evolution with three memory sizes: no memory, limited memory and unlimited memory.

In the unlimited memory trials each robot saved every learned meme, so the meme pool across the whole robot population (of four robots) grew as the trial progressed. Thus all learned memes were available to be selected for enaction. In the limited memory trials each robot had a memory capacity of only five learned memes, so that when a new meme was learned the oldest one in the robot's memory was deleted.

The diagram below shows the complete family tree of evolved memes, for one typical run of the limited memory case. At the start of the run the robots were seeded with two memes, shown as 1 and 2 at the top of the diagram. Behaviour 1 was a movement pattern in which the robot traces a triangle path, behaviour 2 a square. Because this was a limited memory trial the total meme pool has only 20 behaviours - these are shown below as diamonds. Notice the cluster of 11 closely related memes at the bottom right, all of which are 7th, 8th or 9th generation descendents of the triangle meme.

Behavioural evolution map following a 4-robot experiment with limited memory; each robot stores only the most recent 5 learned behaviours. Each behaviour is descended from two seed behaviours labelled 1 and 2. Orange nodes are high fidelity copies, blue nodes are low fidelity copies. The 20 behaviours in the memory of all 4 robots at the end of the experiment are highlighted as diamonds. Note the cluster of 11 closely-related behaviours at the bottom right.

When we ran multiple trials of the limited and unlimited memory cases, then analysed the number and sizes of the clusters of related memes in the meme pool, we saw that the limited memory trials showed a smaller number of larger clusters than the unlimited memory case. The difference was clear and significant; with limited memory an average of 2.8 clusters of average size 8.3, with unlimited memory 3.9 clusters of size 6.9.

Why is this clustering interesting? Well it's because the number and size of clusters in the meme pool are good indicators of its diversity. Think of each cluster of related memes as a 'tradition'. A healthy culture needs a balance between stability and diversity. Neither too much stability, i.e. a very small number (in the limit 1) of traditions, or too much diversity, i.e. clusters so small that there are no persistent traditions at all. Perhaps the ideal balance is a smallish number of somewhat persistent traditions.

So far I didn't mention the no memory case. This was the least interesting of the three. Actually by no memory we mean a memory size of one; in other words a robot has no choice but to enact the last behaviour it learned. There is no selection, and no clusters can form. Traditions can never even get started, let alone persist.

Of course it would unwise to draw any big conclusions from this limited experimental study. But an intriguing possibility is that some forgetting (but not too much) may, just like noisy imitation, be a necessary condition for the emergence of culture in social agents.

Full reference:
Erbas MD, Bull L and Winfield AFT (2015), On the Evolution of Behaviors through Embodied Imitation, Artificial Life, 21 (2), pp 141-165. The full text (final draft) paper can be downloaded here.

Related blog posts:
Robot imitation as a method for modelling the foundations of social life
Open-ended Memetic Evolution, or is it?

Towards an Ethical Robot

Several weeks ago I wrote about our work on robots with internal models: robots with a simulation of themselves and their environment inside themselves. I explained that we have built a robot with a real-time Consequence Engine, which allows it to model and therefore predict the consequences of both its own actions, and the actions of other actors in its environment.

To test the robot and its consequence engine we ran two sets of experiments. Our first paper, setting out the results from one of those experiments, has now been published, and will be presented at the conference Towards Autonomous Robotics (TAROS) next week. The paper is called: Towards an Ethical Robot: Internal Models, Consequences and Ethical Action Selection. Let me now outline the work in that paper.

First here is a simple thought experiment. Imagine a robot that's heading toward a hole in the ground. The robot can sense the hole, and has four possible next actions: stand still, turn toward the left, continue straight ahead, or move toward the right. But imagine there's also a human heading toward the hole, and the robot can also sense the human.

From the robot's perspective, it has two safe options: stand still, or turn to the left. Go straight ahead and it will fall into the hole. Turn right and it is likely to collide with the human.








But if the robot, with its consequence engine, can model the consequences of both its own actions and the human's - another possibility opens up: the robot could sometimes choose to collide with the human to prevent her from falling into the hole.

Here's a simple rule for this behaviour:

IF for all robot actions, the human is equally safe
THEN (* default safe actions *)
    output safe actions
ELSE (* ethical action *)
    output action(s) for least unsafe human outcome(s)

This rule appears to match remarkably well with Asimov’s first law of robotics: A robot may not injure a human being or, through inaction, allow a human being to come to harm. The robot will avoid injuring (i.e. colliding with) a human (may not injure a human), but may also sometimes compromise that rule in order to prevent a human from coming to harm (...or, through inaction, allow a human to come to harm). And Asimov's third law: A robot must protect its own existence as long as such protection does not conflict with the First or Second Law.

Well, we tested this scenario with real robots: one robot with consequence engine plus ethical rule (the A-robot - after Asimov), and another robot acting as a proxy human (the H-robot). And it works!

Here's what the real robot experiment looks like. We don't have a real hole. Instead a virtual hole - the yellow shaded square on the right. We just 'tell' the A-robot where the hole is. We also give the A-robot a goal position - at the top right - chosen so that the robot must actively avoid the hole. The H-robot on the right, acting as a proxy human, doesn't 'see' the hole and just heads straight for it. (Ignore the football pitch markings - we're re-using this handy robo-soccer pitch.)

So, what happens? For comparison we ran two trials, with multiple runs in each trial. In the first trial is just the A-robot, moving toward its goal while avoiding falling into the hole. In the second trial we introduce the H-robot. The graphs below show the robot trajectories, capturing by our robot tracking system, for each run in each of the two trials.

In trial 1, see how the A-robot neatly clips the corner of the hole to reach its goal position. Then in trial 2, see how the A robot initially moves toward it's goal, then notices that the H-robot is in danger of falling into the hole, so it diverts from its trajectory in order to head-off H. By provoking a collision avoidance behaviour by H, A sends it off safely away from the hole, before then resuming its own progress toward its goal position. The A-robot is 100% successful in preventing H from falling into the hole.

At this point we started to write the paper, but felt we needed something more than "we built it and it works just fine". So we introduced a third robot - acting as a second proxy human. So now our ethical robot would face a dilemma - which one should it rescue? Actually we thought hard about this question and decided not to programme a rule, or heuristic. Partly because such a rule should be decided by ethicists, not engineers, and partly because we wanted to test our ethical robot with a 'balanced' dilemma.

We set the experiment up carefully so that the A-robot would notice both H-robots at about the same time - noting that because these are real physical robots then no two experimental runs will be exactly identical. The results were very interesting. Out of 33 runs, 16 times the A-robot managed to rescue one of the H-robots, but not the other, and amazingly, 3 times the A-robot rescued both. In those 3 cases, by chance the A-robot rescued the first H-robot very quickly and there was just enough time to get to the second before it reached the hole. Small differences in the trajectories of H and H2 helped here. But perhaps most interesting were the 14 times when the A-robot failed to rescue either. Why is this, when there is clearly time to rescue one? When we studied the videos, we see the answer. The problem is that the A-robot sometimes dithers. It notices one H-robot, starts toward it but then almost immediately notices the other. It changes its mind. And the time lost dithering means the A-robot cannot prevent either robot from falling into the hole. Here are the results.

Trial 3: a robot with an ethical dilemma. Which to save, H or H2?

Here is an example of a typical run, in which one H-robot is rescued. But note that the A-robot does then turn briefly toward the other H-robot before 'giving-up'.

And here is a run in which the A-robot fails to rescue either H-robot, with really great dithering (or bad, if you're an H-robot).

Is this the first experimental test of a robot facing an ethical dilemma?

We set out to experimentally test our robot with a consequence engine, and ended up building a minimally ethical robot which - remarkably - appears to implement Asimov's first and third laws of robotics. But, as we say in the paper, we're not claiming that a robot which apparently implements part of Asimov’s famous laws is ethical in any formal sense, i.e. that an ethicist might accept. But even minimally ethical robots could be useful. I think our approach is a step in this direction.

---

Full paper reference:
Winfield AFT, Blum C and Liu W (2014), Towards an Ethical Robot: Internal Models, Consequences and Ethical Action Selection, pp 85-96 in Advances in Autonomous Robotics Systems, Lecture Notes in Computer Science Volume 8717, Eds. Mistry M, Leonardis A, Witkowski M and Melhuish C, Springer, 2014. Download final draft (pdf).

Acknowledgements:
I am hugely grateful to Christian Blum who programmed the robots, set up the experiment and obtained the results outlined here. Christian was supported by Dr Wenguo Liu.

Related blog posts:
On internal models, consequence engines and Popperian creatures
Ethical Robots: some technical and ethical challenges

On internal models, consequence engines and Popperian creatures

So. We've been busy in the lab the last few months. Really exciting. Let me explain.

For a couple of years I've been thinking about robots with internal models. Not internal models in the classical control-theory sense, but simulation based models; robots with a simulation of themselves and their environment inside themselves, where that environment could contain other robots or, more generally, dynamic actors. The robot would have, inside itself, a simulation of itself and the other things, including robots, in its environment. It takes a bit of getting your head round. But I'm convinced that this kind of internal model opens up all kinds of possibilities. Robots that can be safe, for instance, in unknown or unpredictable environments. Robots that can be ethical. Robot that are self-aware. And robots with artificial theory of mind.

I'd written and talked about these ideas but, until now, not had a chance to test them with real robots. But, between January and June the swarm robotics group was joined by Christian Blum, a PhD student from the cognitive robotics research group of the Humboldt University of Berlin. I suggested Christian work on an implementation on our e-puck robots and happily he was up for the challenge. And he succeeded. Christian, supported by my post-doc Research Fellow Wenguo, implemented what we call a Consequence Engine, running in real-time, on the e-puck robot.

Here is a block diagram. The idea is that for each possible next action of the robot, it simulates what would happen if the robot were to execute that action for real. This is the loop shown on the left. Then, the consequences of each of those next possible actions are evaluated. Those actions that have 'bad' consequences, for either the robot or other actors in its environment, are then inhibited.

This short summary hides alot of detail. But let me elaborate on two aspects. First, what do I mean by 'bad'? Well it depends on what capability we are trying to give the robot. If we're making a safer robot, 'bad' means 'unsafe'; if we're trying to build an ethical robot, 'bad' would mean something different - think of Asimov's laws of robotics. Or bad might simply mean 'not allowed' if we're building a robot whose behaviours are constrained by standards, like ISO 13482:2014.

Second, notice that the consequence engine is not controlling the robot. Instead it runs in parallel. Acting as a 'governor', it links with the robot controller's action selection mechanism, inhibiting those actions evaluated as somehow bad. Importantly the consequence engine doesn't tell the robot what to do, it tells it what not to do.

Running the open source 2D robot simulator Stage as its internal simulator our consequence engine runs at 2Hz, so every half a second it is able to simulate about 30 next possible actions and their consequences. The simulation budget allows us to simulate ahead around 70cm of motion for each of those next possible actions. In fact Stage is actually running on a laptop, linked to the robot over the fast WiFi LAN. But logically it is inside the robot. What's important here is the proof of principle.

Dan Dennett, in his remarkable book Darwin's Dangerous Idea, describes the Tower of Generate-and-Test; a conceptual model for the evolution of intelligence that has become known as Dennett's Tower.

In a nutshell Dennett's tower is set of conceptual creatures each one of which is successively more capable of reacting to (and hence surviving in) the world through having more sophisticated strategies for 'generating and testing' hypotheses about how to behave. Read chapter 13 of Darwin's Dangerous Idea for the full account, but there are some good précis to be found on the web; here's one. The first three storeys of Dennett's tower, starting on the ground floor, have:

• Darwinian creatures have only natural selection as the generate and test mechanism, so mutation and selection is the only way that Darwinian creatures can adapt - individuals cannot.
• Skinnerian creatures can learn but only by literally generating and testing all different possible actions then reinforcing the successful behaviour (which is ok providing you don't get eaten while testing a bad course of action).
• Popperian creatures have the additional ability to internalise the possible actions so that some (the bad ones) are discarded before they are tried out for real.

Like the Tower of Hanoi each successive storey is smaller (a sub-set) of the storey below, thus all Skinnerian creatures are Darwinian, but only a sub-set of Darwinian creatures are Skinnerian and so on.

Our e-puck robot, with its consequence engine capable of generating and testing next possible actions, is an artificial Popperian Creature: a working model for studying this important kind of intelligence.

In my next blog post, I'll outline some of our experimental results.

---

Acknowledgements:
I am hugely grateful to Christian Blum who brilliantly implemented the architecture outlined here, and conducted experimental work. Christian was supported by Dr Wenguo Liu, with his deep knowledge of the e-puck, and our experimental infrastructure.

Related blog posts:

Ethical Robots: some technical and ethical challenges
Robot know thyself

Walterian Creatures

Noisy imitation speeds up group learning

Broadly speaking there are two kinds of learning: individual learning and social learning. Individual learning means learning something entirely on your own, without reference to anyone else who might have learned the same thing before. The flip side of individual learning is social learning, which means learning from someone else. We humans are pretty good at both individual and social learning although we very rarely have to truly work something out from first principles. Most of what we learn, we learn from teachers, parents, grandparents and countless others. We learn everything from how to make chicken soup to flying an aeroplane from watching others who already know the recipe (or wrote it down), or have mastered the skill. For modern humans I reckon it’s pretty hard to think of anything we have truly learned, on our own; maybe learning to control our own bodies as babies, leading to crawling and walking are candidates for individual learning (although as babies we are surrounded by others who already know how to walk – would we walk at all if everyone else got around on all fours?). Learning to ride a bicycle is perhaps also one of those things no-one can really teach you – although it would be interesting to compare someone who has never seen a bicycle, or anyone riding one, in their lives with those (most of us) who see others riding bicycles long before climbing on one ourselves.

In robotics we are very interested in both kinds of learning, and methods for programming robots that can learn are well known. A method for individual learning is called reinforcement learning (RL). It’s a laborious process in which the robot tries out lots and lots of actions and gets feedback on whether each action helps or hinders the robot in getting closer to its goal – actions that help/hinder are re/de-inforced so the robot is more/less likely to try them again; it’s a bit like shouting “warm, hot, cold, colder…” in a hide-and-seek game. It’s fair to say that RL in robotics is pretty slow; robots are not good individual learners, but that's because, in general, they have no prior knowledge. As a fair comparison think of how long it would take you to learn how to make fire from first principles if you had no idea that getting something hot may, if you have the right materials and are persistent, create fire, or that rubbing things together can make them hot. Roboticists are also very interested in developing robots that can learn socially, especially by imitation. Robots that you can program by showing them what to do (called programming by demonstration) clearly have a big advantage over robots that have to be explicitly programmed for each new skill.

Within the artificial culture project PhD student (now Dr) Mehmet Erbas developed a new way of combining social learning by imitation and individual reinforcement learning, and the paper setting out the method together with results from simulation and real robots has been published in the journal Adaptive Behavior. Let me explain the experiments with real robots, and what we have learned from them.

Here's our experiment. We have two robots - called e-pucks. The inset shows a closeup. Each robot has its own compartment and must - using individual (reinforcement) learning - learn how to navigate from the top right hand corner, to the bottom left hand corner of its compartment. Learning this way is slow, taking hours. But in this experiment the robots also have the ability to learn socially, by watching each other. Every so often one of the robots will stop its individual learning and drive itself out of its own compartment, to the small opening at the bottom left of the other compartment. There it will stop and simply watch the other robot while it is learning, for a few minutes. Using a movement imitation algorithm the watching robot will (socially) learn a fragment of what the other robot is doing, then combine this knowledge into what it is individually learning. The robot then runs back to its own compartment and resumes its individual learning. We call the combination of social and individual learning 'imitation enhanced learning'.

In order to test the effectiveness of our new imitation enhanced learning algorithm we first run the experiment with the imitation turned off, so the robots learn only individually. This gives us a baseline for comparison. We then run two experiments with imitation enhanced learning. In the first we wait until one robot has completed its individual learning, so it is an 'expert'; the other robot then learns - using its combination of individual learning and social learning from the expert. Not surprisingly learning this way is faster.

This graph shows individual learning only as the solid black line, and imitation-enhanced learning from an expert as the dashed line. In both cases learning is more or less complete when the graphs transition from vertical to horizontal. We see that individual learning takes around 360 minutes (6 hours). With the benefit of an expert to watch, learning time drops to around 60 minutes.




The second experiment is even more interesting. Here we start the two robots at the same time, so that both are equally inexpert. Now you might think it wouldn't help at all, but remarkably each robot learns faster when it can observe, from time to time, the other inexpert robot, than when learning entirely on its own. As the graph below shows, the speedup isn't as dramatic - but imitation enhanced learning is still faster.

Think of it this way. It's like two novice cooks, neither of whom knows how to make chicken soup. Each is trying to figure it out by trial and error but, from time to time, they can watch each other. Even though its pretty likely that each will copy some things that lead to worse chicken soup, on average and over time, each hapless cook will learn how to make chicken soup a bit faster than if they were learning entirely alone.



In the paper we analyse what's going on when one robot imitates part of the semi-learned sequence of moves by the other. And here we see something completely unexpected. Because the robots imitate each other imperfectly - when one robot watches another and then tries to copy what it saw, the copy will not be perfect - from time to time, one inexpert robot will miscopy the other inexpert robot and the miscopy, by chance, helps it to learn. To use the chicken soup analogy: it's as if you are spying on the other cook - try to copy what they're doing but get in wrong and, by accident, end up with better chicken soup.

This is deeply interesting because it suggests that when we learn in groups making mistakes - noisy social learning - can actually speed up learning for each individual and for the group as a whole.

Full reference:
Mehmet D Erbas, Alan FT Winfield, and Larry Bull (2013), Embodied imitation-enhanced reinforcement learning in multi-agent systems, Adaptive Behavior. Published online 29 August 2013. Download pdf (final draft)

When robots start telling each other stories...

About 6 years ago the late amazing Richard Gregory said to me, with a twinkle in his eye, "when your robots start telling each other stories, then you'll really be onto something". It was a remark with much deeper significance than I realised at the time.

Richard planted a seed that's been growing since. What I didn't fully appreciate then, but do now, is the profound importance of narrative. More than we perhaps imagine. Narrative is, I suspect, a fundamental property of both human societies and individual human beings. It may even be a universal property of all advanced societies of sentient social beings. Let me try and justify this outlandish claim. First, take human societies. We humans love to tell each other stories. Whether our stories are epic poems, love songs; stories told with sound (music), or movement (dance), or with stuff (sculpture or art). Stories about what we did today, or on our holidays, stories made with images (photos, or movies); true stories or fantasies, or stories about the Universe that strive to be true (science), or very formal abstract stories told with mathematics, stories are everywhere. Arguably human culture is mostly stories.

Since humans started remembering stories and passing them on orally, and more recently with writing, we have had history: the more-or-less-true grand stories of human civilisation. Even the many artefacts of our civilisation are kinds of stories. They are embodied stories, which narrate the process by which they were designed and made; the plans and drawings which we use to formally record those designs are literally stories which tell how to arrange and join materials in space to fashion the artefact. Project plans are narratives of a different kind: they tell the story of the future steps that must be taken to achieve a goal. Computer programs are stories too. Except that they contain multiple narratives (bifurcated with branches and reiterated with loops), whose paths are determined by input data, which are related over and over at blinding speed within the computer. 

Now consider individual humans. There is a persuasive view in psychology that each of us owes our identity, our sense of self, to our personal life stories. The physical stuff that makes us, the cells of our body, are regenerated and replaced continuously, so that there's very little of you that existed 5 years ago. (I just realised the fillings in my teeth are probably the oldest part of me!) Yet you are still you. You feel like the same you 10, 20 or in my case 50 years ago - since I first became self-aware. I think that it's the lived and remembered personal narrative of our lives that provides us with the feeling, the illusion if you like, of a persistent self. This is I think why degenerative brain diseases are so terrifying. They appear to eat away that personal narrative so devastatingly that the person is ultimately lost, even while their physical body continues living.

So I was tremendously excited to be invited to a cross-disciplinary workshop on Narrative and Complex Systems at the York Centre for Complex Systems Analysis a couple of weeks ago, co-organised by York Professors of English Richard Walsh, and Computer Science Susan Stepney. For the first time I found myself in a forum in which I could share and debate ideas on narrative.

In preparing for the workshop I realised that perhaps the idea of robots telling each other stories isn't as far fetched as it first appears. Think about a simple robot, like the e-puck. What does the story of its life consist of? Well, it is the complete history of all of the movements, including turns, etc, punctuated by interactions with its environment. Because the robot and its set of behaviours is simple, then those interactions are pretty simple too. It occurred to me that it is perfectly possible for a robot to remember everything that has ever happened to it. Now place a number of these robots together, in a simple 'society' of robots, and provide them with the mechanism to exchange 'life stories' (or more likely, fragments of life stories). This mechanism is something we already developed in the Artificial Culture project - it is social learning by imitation. These robots would be telling each other stories.

But, I hear you ask, would these stories have any meaning? Well, to start with I think we must abandon the notion that they would necessarily mean anything to us humans. After all, these are robots telling each other stories. Ok, so would the stories mean anything to the robots themselves, especially robots with limited 'cognition'? Now we are in the interesting territory of semiotics, or - to be more accurate - robosemiotics. What, for instance, would one robot's story signify to another? That signification would I think be the meaning. But I think to go any further we would need to do the robot experiment I have outlined here.

And what would be the point of my proposed robot experiment? It is, I suggest, this:

to explore, with an abstract but embodied model, the relationship between the narrative self and shared narrative, i.e. culture.

By doing this experiment would we be, as Richard Gregory suggested, really onto something?

Swarm robotics at the Science Museum

Just spent an awesomely busy weekend at the Science Museum, demonstrating Swarm Robotics. We were here as part of the Robotville exhibition, and - on the wider stage - European Robotics Week. I say we because it was a team effort, led by my PhD student Paul O'Dowd who heroically manned the exhibit all four days, and supported also by postdoc Dr Wenguo Liu. Here is a gallery of pictures from Robotville on the science museum blog, and some more pictures here (photos by Patu Tifinger):

Although exhausting, it was at the same time uplifting. We had a crowd of very interested families and children the whole time - in fact the organisers tell me that Robotville had just short of 8000 visitors over the 4 days of the exhibition. What was really nice was that the whole exhibition was hands-on, and our sturdy e-puck robots - at pretty much eye-level for 5-year olds, attracted lots of small hands interacting with the swarm. A bit like putting your hand into an ants nest (although I doubt the kids would have been so keen on that.)

Let me explain what the robots were doing. Paul had programmed two different demonstrations, one with fixed behaviours and the other with learning.

For the fixed behaviour demo the e-puck robots were programmed with the following low-level behaviours:

1. Short-range avoidance. If a robot gets too close to another robot or an obstacle then it turns away to avoid it.
2. Longer-range attraction. If a robot can sense other robots nearby but gets too far from the flock, then it turns back toward the flock. And while in a flock, move slowly.
3. If a robot loses the flock then it speeds up and wanders at random in an effort to regain the flock (i.e. another robot).
4. While in a flock, each robot will communicate (via infra-red) its estimate of the position of an external light source to nearby robots in the flock. While communicating the robot flashes its green body LED.
5. Also while in a flock, each robot will turn toward the 'consensus' direction of the external light source.

The net effect of these low-level behaviours is that the robots will both stay together as a swarm (or flock), and over time, move as a swarm toward the external light source. Both of these swarm-level behaviours are emergent because they result from the low-level robot-robot and robot-environment interactions. While the flocking behaviour is evident in just a few minutes, the overall swarm movement toward the external light source is less obvious. In reality even the flocking behaviour appears chaotic, with robots losing each other, and leaving the flock, or several mini-flocks forming. The reason for this is that all of the low-level behaviours make use of the e-puck robots' multi-purpose Infra-red sensors, and the environment is noisy; in other words because we don't have carefully controlled lighting there is lots of ambient IR light constantly confusing the robots.

The learning demo is a little more complex and makes use of an embedded evolutionary algorithm, actually running within the e-puck robots, so that - over time - the robots learn how to flock. This demo is based on Paul's experimental work, which I described in some detail in an earlier blog post, so I won't go into detail here. It's the robots with the yellow hats in the lower picture above. What's interesting to observe is that initially, the robots are hopeless - constantly crashing into each other or the arena walls, but noticeably over 30 minutes or so we can see the robots learn to control themselves, using information from their sensors. The weird thing here is that, every minute or so, each robot's control software is replaced by a great-great-grand child of itself. The robot's body is not evolving, but invisibly its controller is evolving, so that later generations of controller are more capable.

The magical moment of the two days was when one young lad - maybe 12 years old, who very clearly understood everything straight away and seemed to intuit things I hadn't explained - stayed nearly an hour explaining and demonstrating to other children. Priceless.

New experiments in embodied evolutionary swarm robotics

My PhD student Paul has started a new series of experiments in embodied evolution in the swarm robotics lab. Here's a picture showing his experiment with 3 Linux e-puck robots in a small circular arena together with an infra-red beacon (at about 2 o'clock).



The task the robots are engaged in collective foraging for food. Actually there's nothing much to see here because the food items are virtual (i.e. invisible) blobs in the arena that the robots have to 'find', then 'pick up' and 'transport' to the nest (again virtually). The nest region is marked by the infra-red beacon - so the robots 'deposit' the food items in the pool of IR light in the arena just in front of the beacon. The reason we don't bother making physical food items and grippers, etc, is that this would entail engineering work that's really not important here. You see, here we are not so interested in collective foraging - it's just a test problem for investigating the thing we're really interested in, which is embodied evolution.

The point of the experiment is this: at the start the robots don't know how to forage for food; during the experiment they must collectively 'evolve' the ability to forage. Paul is here researching the process of collective evolution. Before explaining what's going on 'under the hood' of these robots, let me give some background. Evolutionary robotics has been around for nearly 20 years. The idea is that instead of hand-designing the robot's control system we use an artificial process inspired by Darwinian evolution, called a genetic algorithm. It's really a way of automating the design. Evolutionary algorithms have been shown to be a very efficient way of searching the so-called design space and, in theory, will come up with (literally evolve) better solutions than we can invent by hand. Much more recent is the study of evolutionary swarm robotics (which is why there's no Wikipedia entry yet), which tackles the harder problem of evolving the controllers for individual robots in a swarm such that, collectively, the swarm will self-organise to solve the overall task.

Still with me? Good. Now let me explain what's going on in the robots of Paul's experiment. Each robot has inside it a simulation of itself and it's environment (food, other robots and the nest). That simulation is not run once, but many times over within a genetic algorithm inside the robot. Thus each robot is running a simulation of the process of evolution, of itself, in itself. When that process completes (about once a minute), the best performing evolved controller is transferred into the real robot's controller. Since the embodied evolutionary process runs through several (simulated) generations of robot controller, then the final winner of each evolutionary competition is, in effect, a great great... grandchild of the robot controller at the start of each cycle. While the real robots are driving around in the arena foraging (virtual) food and returning it to the nest, simulated evolution is running - in parallel - as a background process. Every minute or so the real robot's controllers are updated with the latest generation of (hopefully improved) evolved controllers so what we observe is the robots gradually getting better and better at collective foraging. If you think this sounds complicated – it is. The software architecture that Paul has built to accomplish this is ferociously complex and all the more remarkable because it fits within a robot about the size of a salt shaker. But in essence it is like this: what’s going on inside the robots is a bit like you imagining lots of different ways of riding a bike over and over, inside your head, while actually riding a bike.

Putting a simulation inside a robot is something roboticists refer to as ‘robots with internal models’ and if we are to build real-world robots that are more autonomous, more adaptable – in short smarter, this kind of complexity is something we will have to master.

If you’ve made it this far, you might well ask the question, “what if the simulation inside the robot is an inaccurate representation of the real world – won’t that mean the evolved controller will be rubbish?” You would be right. One of the problems that has dogged evolutionary robotics is known as the 'reality gap'. It is the gap between the real world and the simulated world, which means that a controller evolved (and therefore optimised) in simulation typically doesn't work very well - or sometimes not at all - when transferred to the real robot and run in the real world. Paul is addressing this hard problem by also evolving the embedded simulators at the same time as evolving the robot's controllers; a process called co-evolution. This is where having a swarm of robots is a real advantage: just as we have a population of simulated controllers evolving inside each robot, we have a population of simulators - one per robot - evolving collectively across the swarm.

---

Related blog posts:
Environment-driven distributed evolutionary adaptation
Walterian creatures

New video of 20 evolving e-pucks

In June I blogged about Nicolas Bredeche and Jean-Marc Montanier working with us in the lab to transfer their environment-driven distributed evolutionary adaptation algorithms to real robots, using our Linux extended e-pucks. Nicolas and Jean-Marc made another visit in August to extend the experiments to a larger swarm size, of 20 robots; they made a YouTube movie and here it is:



In the narrative on YouTube Nicolas writes

This video shows a fully autonomous artificial evolution within a population of ~20 completely autonomous real (e-puck) robots. Each robot is driven by its "genome" and genomes are spread whenever robots are close enough (range: 25cm). The most "efficient" genomes end up being those that successfully drive robots to meet with each other while avoiding getting stuck in a corner.

There is no human-defined pressure on robot behavior. There is no human-defined objective to perform.

The environment alone puts pressure upon which genomes will survive (ie. the better the spread, the higher the survival rate). Then again, the ability for a genome to encode an efficient behavioral strategy first results from pure chance, then from environmental pressure.

In this video, you can observe how going towards the sun naturally emerges as a good strategy to meet/mate with other (it is used as a convenient "compass") and how changing the sun location affect robots behavior.

Note: the 'sun' is the static e-puck with a white band around it.

Open-hardware Linux e-puck extension board published

It's now over two years since I first blogged about our Linux-enhanced e-puck, designed by my colleague Dr Wenguo Liu. Since then, the design has gone through several improvements and is now very stable and reliable. We've installed the board on all 50 of our e-puck robots and it has also been adopted for use in swarm robotics projects by Jenny Owen at York, Andy Guest at Abertay Dundee and Newport.

Since the e-puck robot is open-hardware, Wenguo and I were keen that our extension board should follow the same principle, and so the complete design has been published online at sourceforge here http://lpuck.sourceforge.net/. All of the hardware designs, together with code images and an excellent installation manual written by Jean-Charles Antonioli are here.


















Here's a picture of the extension board. The big chip is an ARM9 microcontroller and the small board hanging off some wires is the WiFi card (in fact it's a WiFi USB stick with the plastic casing removed).

And here is a picture of one of our e-pucks with the Linux extension board fitted, just above the red skirt. The WiFi card is now invisible because it is fitted neatly into a special slot on the underside of the yellow 'hat'.

The main function of the yellow hat is the matrix of pins on the top, that we use for the reflective spheres needed by our Vicon tracking system to track the exact position of each robot during experiments. You can see one of the spheres very strongly reflecting the camera flash in this photo. The function of the red skirt is so that robots can see each other, with their onboard cameras. You can see the camera in the small hole in the middle of the red skirt. Without the red skirt the robots simply don't see each other too well, at least partly because of their transparent bodies.

---

postscript (added Feb 2011): Here's the reference to our paper describing the extension board:
Liu W, Winfield AFT, 'Open-hardware e-puck Linux extension board for experimental swarm robotics research', Microprocessors and Microsystems, 35 (1), 2011, doi:10.1016/j.micpro.2010.08.002.