Dedale

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.

Discrete env : Groix Island (OSM)

Discrete env : Groix Island (OSM)

3D Continious env : Auvergne

3D Continious env : Auvergne

Hand-made discrete env

Hand-made discrete env

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.

Citing Dedale

Cédric Herpson. Dedale: A Realistic Simulation Framework for Decentralized Multi-Agents Problems. (to appear - draft version :hal-02392383)

1. Environnement

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 :

Hand-made

Hand-made

Grid-world

Grid-world

Dogoronev generated env

Dogoronev based

Barabasi generated env

Barabasi based

Hunting ground

Designed Hunting ground

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

1.1 Wells

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.

1.2 Treasures

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.

2. Agents

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(+1) 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
  • HumanControlled : Only one agent can be of this type, it is used to locally test the behaviour of your team facing a keyboard-controlled agent

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 occurrence, if any, of a treasure, its type, value and opening 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 ?

Tips :

  • 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 ?

Tips :

  • 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 ?

Tips :

  • 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..