Lab description:
Experiments with multi-agent systems using mobile robots. Used primarily in student projects (bachelor and master projects). From spring 2010 used in the CDIO project course for 4th semester IT Diploma students. The lab is sponsered by the DTU Informatics strategic fund.
Lab location:
Building 322, Room 133.
Lab access:
To acquire access please contact the lab responsibles, see below. Access is only given to people doing projects in the lab. Access requires a special key card.
Current hardware:
- 11 LEGO Mindstorms NXT robots.
- 1 PC with Windows/Linux dual boot. 100 m range bluetooth.
- 10 Hitechnic color sensors.
- 5 Hitechnic compass sensors.
- 10 Hitechnic hi-precision IR distance sensors.
- 7 Lego NXT ressource sets.
- 10 Mindsensors dual infrared obstacle detector.
- 2 Mindsensors PSP-Nx combo with wireless controller.
- 1 Mindsensors vision subsystem.
Projects completed in the lab (with links to project reports):
Multi Agent Robotics.
Bachelor project autumn 2006.
Anders Lemke, Johan Laidlaw and Lars Zilmer-Pedersen.
Description: The project implements a multi-agent system based on a collection of Lego NTX robots. The agents (robots) are implemented using the so-called BDI architecture, which is currently one of the most popular software models for programming intelligent agents. The robots navigate in a grid-based world and use the A*-algorithm for path finding. Communication between the agents is via bluetooth connections using messages conforming to the FIPA Agent Communication Language Specifications. As part of the project an advanced C# library for communicating with and controlling the robots is implemented.
The robots solve the following problem. They are divided into two teams, black and silver. A number of objects are placed on (some of) the grid cross sections. These objects are also divided into black and silver. The robots can pick up the objects using a claw whose physical design is based on the Lego NXT Tribot described by Lego. It is assumed that only black team robots can pick up black objects and only silver team robots can pick up silver objects. Furthermore, the robots do not in advance know where the different objects are placed on the grid. The goal of the robots is to find all objects and move them out of the grid. Many concrete scenarios can only be solved if the two teams collaborate, e.g. if the path of a black team robot is blocked by a silver object. In this way, the problem makes a nice testbed for experimenting with various issues in multi-agent communication and collaboration.
Multi-Agent Robotic Systems.
Specialisation course spring 2007.
Christian Agerbeck.
Description: The projects implements a predator-prey domain (pursuit domain), where a group of robots (the predators) have to capture another robot (the prey). The robots navigate in a grid-based world as in the project described above, and they are also implemented using a BDI architecture. The predator robots are equipped with a ultra-sonic sensor to help them locate the prey. The implementation uses the C# library developed in the project described above.
The robots solve the following problem. They are divided into two teams, predators and prey. There is usually only one prey. The predators don't know the location of the prey in advance. A corner cube reflector is mounted on the prey so that the predators can (approximately) locate the prey with their ultra-sonic sensors. The goal is then for the predators to locate and capture the prey. In this project a capture is defined as a situation in which the prey is surrounded by predators and cannot move to any neighboring cross sections in the grid.
Planning with LEGO agents.
Bachelor project spring 2007.
Bo Kanstrup Hansen and Anders Rasmussen.
Description: The project implements an automated planning algorithm for controlling the Lego NXT robots in the grid-based world described above. The planning algorithm implemented is POP*, a partial-order planner (POP) with search inspired by the A* path finding algorithm. The physical design of the robots is as in the project Multi Agent Robotics with a claw to pick up objects. The robots navigate in a grid-based world as in the previously described projects.
The robots solve the following problem. Using the planner they can solve an arbitrary goal given in the form of a list of conditions to be satisfied. Such conditions can e.g. be to get certain objects into certain positions. Thus the framework is more general and flexible than the one in the project Multi Agent Robotics described above. However, since there is no substantial coordination between the plans of the individual agents, problems such as deadlocks can appear in the multi-agent variant of the scenario (each individual agent makes its own plans).
Artificial intelligence in the predator/prey domain.
Master's project spring 2008.
Frej Laursen Würtz.
Description: The project implements a predator/prey domain as in the project Multi-Agent Robotic Systems described above. However, in this project the position of the prey is always supposed to be known, that is, the predators are assumed to have a way of efficiently tracking the prey. The project extends the previous iMARS projects in several ways. First of all, this is the first project in which a simulator has been implemented to perform completely software-based simulations of the robot scenario. The simulator uses the same communication protocol for the communication between the simulated robots and the simulated server as in the physical robot environment. This makes it significantly simpler to port an implemented multi-agent system from the simulator to the physical robot environment. Another extension compared to the previous projects is the idea of having "replaceable" AIs on the robots. The AI of each individual robot is constructed as a separate module, and this module can be replaced with another if required. This can for instance be used to duplicate AIs that turn out to be efficient to other robots. It also makes it possible to experiment with letting different robots within the multi-agent system have different types of AIs based on different AI techniques.
A third extension compared to the previous projects is an improvement of the grid-based world that the robots navigate in. Previously the robots were navigating by simple line-following of a grey line on the grid. However, since only one color sensor is used for the line-following, this only provides a primitive binary measurement (robot on the line/robot not on the line). In the new setup, three colors are used: a white line in the middle, a blue stripe on one side of the line and a red stripe on the other side. This gives a ternary measurement (robot on the line/robot to the left of the line/robot to the right of the line). This increases stability of the robot line-following and also does away with the need to do back-and-forth sweeping whenever the robot no longer sees the line. Finally, the present project is the first to use a physical design of the robots not being a variant of the Lego NXT Tribot. The robots of this project use caterpillar tracks instead of wheels. This improves stability in all movements, in particular, 90 and 180 degree turns become significantly more precise.
The robots solve the following problem. Two predators have the common goal of capturing the prey. They navigate in a grid-based world that can contain an arbitrary number of obstacles. The positions of the obstacles are known in advanced. By using obstacles, any maze-like environment can be modelled (e.g. the maze used in the original Pac-Man game, which is an early example of a predator/prey domain using very basic AI).
Watch the video demo of this project (2 predators, 1 prey).
Multi-Agent Robotics using LEGO NXT Robots.
Bachelor project spring 2008.
Andreas Møller and David Emil Lemvigh.
Description: The project is primarily concerned with the localisation problem for the Lego NXT robots. In this project the grid-based world is not used. The robots navigate freely on a floor with no navigation marks. Localisation is done with a system based on an MCS crickets wireless indoor localisation system. A cricket is a small hardware device used for localisation based on a combination of ultrasound and radio frequency technologies. The setup used in the project consists of four listener crickets placed in the ceiling in a rectangular pattern and one beacon cricket on each of the robots. The crickets use time difference of arrival of signals to calculate the distances between all beacons and listeners. Applying simple geometry to these calculated distances allows one to estimate the position of the robots. The robots are physically designed as tanks with two rubber band shooting guns. Each robot is mounted with a compass sensor to determine the direction it is heading, as this information can not be derived from the cricket data.
The project is the first to use leJOS NXJ, a Java programming environment for the Lego NXT robots. LeJOS NXJ includes a replacement firmware for the Lego NXT robots containing a tiny Java Virtual Machine (JVM). This allows the robots to be programmed in Java. LeJOS NXJ also contains a extensive and well-documented library that makes it simpler to program the robots and the comunication between PC and robots. LeJOS NXJ replace the locally developed C# library used in all previous projects.
The robots solve the following problem. The robots can be ordered to move to any position, turn to any angle and fire the guns. Originally, it was intended that the robots should be able to autonomously engage in combat with other robots, but time didn't allow the development of appropriate AI algorithms.
Vehicle Routing Problem for Mobile Hospital Robots.
Bachelor project spring 2009.
Anders Hersland and Emil Kjer.
Description: The project solves a vehicle routing problem with pickup and delivery (VRPPD) for the Lego NXT robots. The domain is a simulation of the tunnel system below Bispebjerg Hospital in Copenhagen. The hospital employs the tunnel system to carry out a large number of transportation tasks of food, medicine, blood samples, mail, etc. The actual transportation is taken care of by small trucks with manual drivers. The hospital would like to be able to replace these trucks and their drivers by autonomous robots, thereby reducing the manpower required for solving the transportation tasks. The present project uses Lego NXT robots to simulate a possible solution to the problem. The robots navigate in a grid-based world representing the tunnel system under the hospital. The project uses leJOS NXJ as in the previous project.
The robots solve the following problem. An arbitrary number of robots is presented with an arbitrary number of transportation tasks to be carried out. Each transportation task is formulated as a task of moving some object from one pickup-and-delivery point to another. For simplicity, the set of pickup-and-delivery points are simply taken to be the cross sections of the grid. The problem is solved primarily by using methods from operations research (OR). The problem is formulated as a minimisation problem, and it is solved using simulated annealing. The physical design of the robots is kept simple in this project, so they need to be loaded and unloaded manually.
Watch the video demo of this project (3 robots, 5 tasks).
Lab responsible:
Thomas Bolander ()
Paul Fischer ()