I'm working on exploration of indoor environments by a team of mobile agents. We use a team of robots to explore the inside of a building in case of a hazardous event, for example fires, gas leaks and so on. We simulate it here, and are talking with a professor in Vienna who is trying to build the robots.I am researching the algorithm to make the robots move inside the building. So for example if we have an area for which we don't have a map, we have this team of robots, and we cannot assume that they can always communicate with each other, because in an indoor environment or in the London Underground for example, they can't always keep in touch with each other. And we cannot assume that they could use GPS positioning because they're indoors. So they try to leave 'traces' in the form of RFID tags, with which they can communicate with each other, saying for example 'We've been in this room'. This can be used to find victims or hazards, so that we can create a map of the building and the first responders can go directly to find the victims, and avoid the hazards.
With sensors, the robots can know for example where a wall is, but we are trying to keep it simple, not to make too many assumptions or too expensive robots. But they leave the RFID tags as a trail of where they have been - so they can communicate with each other using the environment itself.
ASSENT is the name of our group, and I'm working with Niki Trigoni , a lecturer at Birkbeck, on this project. It is called RED-WSN , for Real-time Event Detecion in Wireless Sensor Networks.
The other project in the group is called TIME-EACM , which is about traffic monitoring in the city of Cambridge - part of a big project they are doing with Cambridge University, also involving sensor networks. They try to monitor the traffic in a city to prevent traffic congestion - to show where the traffic is heaviest, identify alternative routes. They are concentrating on gathering data; with sensor networks you are heavily constrained in both communication and power, so you always have to compress the data to send over a small bandwidth (we use Fourier transforms for this).
We tried testing ant algorithms - inspired by real ants, which is work by people at UCLA. The problem, however, with this algorithm is that we are not able to know when it terminates exactly. For an emergency situation, we have to be as fast as possible of course. Also ants also follow the pheromone trails left by others, but we need them to spread out as much as possible.
So we moved to a 'multiple depth first' search, which is a depth first search using multiple agents. But we are not very satisfied with it because the agents can for example be trapped - not able to move because other agents around are exploring the same area; they don't want to go into an area already explored by others so they are blocked.
Finally we came up with an algorithm we call Brick and Mortar, based upon the errors we found from the other ones. So we try to coordinate all the agents and to explore all the area as fast as possible so as not to block each agent. For example, we want to know when they have explored a room so they don't have to go back again if nothing interesting is in there.
We use cells - divide the environment into a grid - so that they can tag each cell if they've been there. If there is a room with only one door, we only need one agent to come explore it. We also have this idea of corridors - so for example if we have a central room with many doors, we need to maintain a network of 'exploring' cells where some agents have been but may need to traverse again to get to others.I am writing my first paper on this work, which is part of my PhD; I just started in April. I came from Bologna University, and I was born a bit south of there. I got my Masters in Computer Engineering, working on artificial intelligence and multimedia databases. In my thesis I used a machine learning algorithm to label pictures, so that for example using an ontology and a database with a lot of images, some labeled but most not - I used this algorithm to label the unlabeled ones, starting from the labeled ones by comparing the patterns, colours, shapes, textures.
[you can try a simulation for yourself and learn more at http://www.dcs.bbk.ac.uk/~assent/Red-Wsn/applet.html ]
Ettore Ferranti