Multi-agent systems
Project assignment, 2019
Tom Holvoet, Hoang Tung Dinh
{tom.holvoet, hoangtung.dinh}@cs.kuleuven.be
1 Introduction
This document describes the project assignment for the course on multi-agent
systems. The objectives of this project are to get insight in various techniques for
developing multi-agent systems, and to conduct scientific study in this domain.
For this project, you can choose one of three options. Either you focus on
studying a MAS-based solution for a pickup-and-delivery problem using RinSim.
Alternatively, you can opt for studying multi-agent planning algorithms in a
relevant scenario of your choice. More explanation on these two options are
provided below.
Thirdly, you may define a different topic for your project. In this case, you
need approval from the didactic team before elaborating on the idea. You can
make an appointment for this, or discuss your idea during the ‘feedback ses-
sion’ (see below). Obviously, your suggestion will have to be on par with the
complexity of the other options. You could e.g. choose to study integrating
e.g, learning techniques such as neural networks, genetic programming, mathe-
matical programming, etc. in MAS-based solutions when these are linked with
topics that were covered in this course (agent architectures, automated planning,
coordination mechanisms).
2 MAS-based solution for Pickup-and-devivery
Route planning and task allocation are two problems that are faced when con-
trolling a fleet of autonomous vehicles such as AGVs (automated guided ve-
hicles) (Vis, 2006). Route planning concerns finding a route for a vehicle such
that the vehicle arrives in time for the task to be performed while conforming to
safety requirements such as keeping safe distance and avoiding collisions. Task
allocation concerns the assignment of vehicles to tasks. The goal of the fleet
of vehicles is to perform all tasks as efficiently as possible, where efficiency is
defined by an objective function which depends on the specific problem.
A typical example of tasks that need to be performed by autonomous vehicles
is the transportation of goods in a warehouse. Requests for transportation
typically arrive dynamically. A request consists of a pickup location, a pickup
time window, a delivery location and a delivery time window. A time window
1
is defined by a begin time indicating the earliest start of servicing and an end
time indicating the latest start of servicing.
Other problems that are often faced with autonomous vehicles, and which
could additionally also be considered, are:
• Battery management - A vehicle’s battery often needs to be charged or
replaced at a specific location. This charging facility is capacitated and
therefore imposes additional constraints on the vehicle’s actions. Also, it
is necessary to make sure that the vehicles always have enough battery to
return to a battery charging station.
• Maintaining a continuous communication link between vehicles in an ad
hoc network, given that the communication range of each vehicles is lim-
ited.
• AGVs need to avoid collisions and deadlock.
2.1 Objectives
For this topic, you are expected to:
• Define a concrete pickup-and-delivery problem (environment, AGVs with
their capabilities, characteristics of tasks, scale, communication constraints,
dynamism, potential AGV crashes, etc.).
• Develop a multi-agent system for a pickup-and-delivery problem domain
using AGVs. This solution should be based on BDI and delegate MAS.
The solution should at least account for both task allocation and route
planning.
• Make a thorough scientific study of the behavior of the MAS (following
the U-model).
You start by clearly defining your own variant of a pickup-and-delivery prob-
lem. It is advised to choose a problem for which RinSim has built-in support to
avoid implementation overhead.
3 Multi-agent planning
Automated planning is key to autonomous agents and multi-agent systems.
There are various ways to model your planning domain (e.g. using deterministic
or non-deterministic models), and various algorithms for planning and their
interaction with agents’ acting behavior.
If you choose this topic for your project, you can - but do not have to - use
RinSim. RinSim could still be useful for running experiments, but when you
feel comfortable developing your own experimentation environment, that is fine
as well.
2
3.1 Objectives
For this topic, you are expected to:
• Define your own planning domain and problem - aim for relatively simple
robots (AGVs, UAVs) in a non-trivial environment, with a considerable
set of actions, and interesting goals;
• Define a solution for both planning and acting, where, for the planning
part, you use one of the following approaches:
– plan-space search approach for partial-order (deterministic) planning
for multi-agent settings;
– non-deterministic model, where you apply determination (a simple
multi-agent setting here is quite a challenge, which is appreciated
but not necessary);
– hierarchical task networks and a multi-agent extension thereof.
• Make a thorough scientific study of the behavior of the MAS (following
the U-model).
Each of these approaches may require some (limited) additional literature search.
Of particular interest in the discussion is the effect that the chosen approach
has on the acting part of the robots.
4 Deliverables
Your submission should consists of:
• a software project, i.e. one zip-file including:
1. source code;
2. if programmed in Java, a mas.jar that can easily be run as ‘java -jar
mas.jar’;
3. if programmed in another language, an executable with a simple (one-
line) README explaining how to start up your system;
• a presentation file (powerpoint, keynote, pdf) for a presentation of appr.
20 minutes, using the following outline:
1. Introduction
(a) objectives
(b) research questions
(c) hypotheses
2. Your multi-agent system design clearly explained
3. Experiments
3
(a) setup
(b) results
(c) analysis
4. Conclusions on your hypotheses, research questions, objectives
5 Practical information
You are expected to work in teams of two people. Please find a partner as soon
as possible, if you are unable to find a partner, use the Toledo forum or email
Prof. Tom Holvoet. If you prefer, you can work alone on the project.
For help with defining your objectives, hypotheses and experiment setup
please refer to chapter 6 of the handbook by Schut (2007) on Toledo.
In April we will organize a ‘feedback session’ where each team has the possi-
bility to discuss their project. You will have a time slot of 5 minutes to present
your project to the didactical team, followed by 10 minutes of discussion. Dur-
ing this meeting we expect you to present your research objectives, research
questions, hypotheses, and how you plan to proceed. The time and place will
be announced via Toledo.
The final submission deadline for your software is Friday, 31 May, 16h59.
At the exam, each group will give a demo (5 minutes) and a presentation
(max. 20 minutes) of the project work. Afterwards, there is an individual
discussion with each team member. Your work will be evaluated based on the
knowledge and insight that you show in the various topics of MAS - the aspects
that were covered in your project as well as other topics that were addressed in
the course.
Please be informed that plagiarism detection software will be applied. Pla-
giarism will be considered as exam fraude.
References
Schut, M. (2007). Scientific handbook for simulation of collection intelligence.
Vis, I. F. (2006). Survey of research in the design and control of auto-
mated guided vehicle systems. European Journal of Operational Research,
170(3):677–709.
