Dedale is an environment for studying multi-agents coordination, learning and decision-making problems under realistic hypotheses. Highly parametrizable, Dedale allows to tackle either cooperative or competitive exploration, patrolling, treasure(s) or agent(s) hunt problems with teams from one to dozens of heterogeneous agents in discrete or continuous environments, local or distributed over the network.
In Dedale the environment is (initially) unknown to the agents. It is dynamic, partially observable and everything is asynchronous (agents and communication). No turn-per-turn here, we consider real-life hypotheses.
Cédric Herpson. Dedale : A Testbed for Multi-Agents Problem-Solving. (to appear - draft version :hal-02392383)
In the discrete case, the environment is a graph. Nodes (each one associated to a unique identifier) are places were your agents find objects and the edges are the corridors between them. You can automatically generate topologies, import OpenStreetMap areas or design yours :
The size of generated environnments is parametrizable. Two agents cannot currently occupy one location at the same time, this is done in order to make you deal with interlocking through coordination.
Elements within the environments
All elements are optional and configurables
Wells are dangerous node where any agent coming-in falls and dies. Wells generate wind in their surrounding nodes (the distance is parametrizable), giving a warning to any passing agent. Depending of the situation, your agents may, or should (not ?) take the risk to explore further.
Treasures of various types, value and difficulty can be automatically distributed or manually set in the environment. A treasure is stored within a safe, which can be locked or not, and added to a node.
If this feature is activated, your agents have to find them and collect as much as possible. When an agent (see next section) is in a room where a treasure is, and if its backPack and expertise allows it, then the agent can grab it.
- If the safe is locked and the agent does not possess sufficient expertise to open it, he needs to call for help.
- If the agent backPack is full or the treasure is of a different type than his, then he grab nothing
- If the agent cannot grab all the treasure, the remaining treasure stays on the map. Another agent can come and take it.
The agent drops a portion of the treasure by picking it up. The more picking actions are made on a treasure, the more the loss is important. We will therefore opt for picking up a single treasure in a minimum of actions.
1.3 Dynamical environment
You can activate adversaries on the map. Thus, several teams can evoluate on the same graph.. But, to begin, we invite you to deal with the Golem. It is currently armless but will move (or steal) the treasures he finds. The coordination of your team will become critical to optimize the picking of the treasures.
At the beginning, agents are deployed (randomly or not) on the map. The agents do not know the topology beforehand. Thus, they have to discover and learn it.
Agents can be of 3 different types :
- Explorer : It cannot collect, only explore
- Tanker : It possess a nearly unlimited storage capacity, but cannot pick anything
- Collector : It possess a backpack specific to a given type of treasure, and a limited carrying capacity. It can pick a treasure, and drop it in the Tanker if the latter is in reach
You can decide to activate one or several type of agents. The more types, the more
difficulties fun ;)
2.1 Limited percepts
When an agent is in a room, it can perceives :
- The id, unique - of the room
- The occurence, if any, of a treasure, its type, value and openning conditions (if any)
- The links to the neighbouring rooms (and associated observations, if any)
2.2 Limited communication range
As your agents are cooperative, they should share their knowledge in order to coordinate and optimize their actions. In order to do that, your agent can communicate through messages. Nevertheless, the reach is limited. An Agent can only communicate with the ones in the neighbourhood (distance that can vary with each agent). The coordination solutions should thus take into account this fact. To control the number (and the size) of the messages exchanged can be a good idea.
2.3 Actions and Observations
The complete description of an agent’s interaction capabilities is available here
3. These configuration possibilities allow you to adress differents research problems :
3.1 Distributed exploration
Consider an unknown finite map, a set of agents and a limited communication range.
- How to efficiently explore it ?
- If we add wells
- How to explore it ?
- What is the minimal number of agents required to locate with certainty the well(s) and fully explore the map ?
- Start with one agent, then 2, 5 and beyond.
- Prefer DFS to BFS.
3.2 Cooperative patrolling and pursuit-evasion games : Hunt the Golem(s)
Consider an unknown finite map, a set of agents and a limited communication range. We release the Golem.
- What strategy can you propose to guarantee to block it on a given node (predetermined or not) in a finite time ?
- What is the minimal number of required agents ?
- Easy on a (finite) binary tree with unlimited communication range, it becomes a little bit more difficult when you set the communication range to 2, use a graph and a annoyingly clever Golem..
- What is the minimal number of required agents on a graph ?
- What are the best strategies ?
- Start with only one golem on a little binary tree
- Draw a picture and remember that the golem will try to get behind your agents
3.3 Treasure(s) hunt and pickup and delivery problems
Consider an unknown map, a set of agents, a limited communication range and treasures to pick (and deliver).
- How to maximise the treasures grabbed ?
- You will need to deal with interlocking
- If the safes have opening conditions
- How to maximise the treasures grabbed ?
- If we release the Golem, he will move the treasures (creating a dynamic environment)
- What strategy can you propose to maximise the treasures grabbed ?
- The Tanker(s) can be in area(s) around a strategical(s) node(s).
Of course, you can activate all of these options at the same time and let other teams compete against you as well..