Modeling problems as DCOPs

What we have seen so far in previous tutorials may seems very theoretical and it might not be obvious how DCOP could be used to solve real-world problems. pyDCOP is meant to be domain-independent, but we hope to convince you that the DCOP algorithms implemented and studied with it can be applied to real applications.

As a topic in the Multi-Agent System field, DCOP are obviously best suited to problems that are distributed in nature. They have been applied to a wide variety of applications, including disaster evacuation [KSL+08], radio frequency allocation [MPP+12], recommendation systems [LdSFB08], distributed scheduling [MTB+04], sensor networks [ZWXW05], intelligent environment [RPR16], [FYP17], smart grid [CPRA15], etc.

When using a DCOP approach on a distributed problem, the first steps are always to cast your problem into an optimization problem and to identify your agents. Then you can select, and probably benchmark, the best algorithm for the settings of your problem. In this tutorial, we will present one way of modelling a target tracking problem as a DCOP.

Example: Target tracking problem

Detecting and tracking mobile objects is a problem with many real applications like surveillance and robot navigation, for example. The goal of such a system is to detect foreign objects as quickly and as many as possible.

The system is made of several sensor scattered in space. Each sensor, for example a small Doppler effect sensor, can only scan a fixed radius around itself at any given time; it has to select with area it operates on.

In an open environment, sensors used in tracking systems usually run on battery, which means they must use as little energy as possible, in order to increase the system operation’s lifetime. This includes switching them-self off and on whenever possible, in a way that does not affect the system’s detection performance.

These sensors are also lightweight devices with limited memory and computation capability. They communicate one with another through radio signals, which may not be reliable. Each sensor can only only communicates with neighboring sensors and has no global information on the whole system.

The overall goal is thus to provide the best detection possible, while preserving energy as much as possible. To achieve this goal, sensors can act on several parameters:

  • selecting which area to scan

  • selecting when to switch on and off

Example: Target tracking DCOP model

Each sensor is controlled by one agent, which decides the sector the sensor is scanning. These agents coordinate in order to plan an efficient scanning strategy ; this problem is actually a distributed planning system.

Let \(S = \{ S_1, ... S_n \}\) be the set of n sensors. Each agent \(S_i\) can select the area to scan among k sectors \(s_i = \{ s_i^1, ... s_i^k \}\).

The agents plan their action over a horizon \(T\) made of \(|T| = t\) time slots. For each time slot, each agent \(S_i\) has to select one action : either scan one of it’s \(s_i^j\) sectors or sleep.

The \(s_i^k\) are our decision variables, whose value represents the sector scanned by a sensor at a given time. These variables take their value from a domain \(D = \{ 1, ... t\}\) ; when the variable \(s_i^k\) takes the value \(t\), it means that the sensor \(S_i\) will scan the sector \(s_i^k\) during the time slot \(t\).

Of course, a sensor can only scan a single sector at any given time. This can be modelled by defining a set of constraints (1) ensuring that two sectors from the same sensor cannot take the same value:

(1)\[\forall s_i^p, s_i^q \in s_i \times s_i, p \neq q \Rightarrow s_i^p \neq s_i^q\]

For an efficient scanning process, we want to avoid several sensors scanning simultaneously the same sector. For this we define a function \(w\) between a pair of sectors \(s_i^p, s_j^q\) where \(w(s_i^p, s_j^q)\) is the surface of the area common to these two sectors. Then we use this function to define constraints (2) between sectors, where the cost of the constraints is this surface, if the sensors of these two sector at scanning at the same time.

(2)\[\begin{split}c(s_i^p, s_j^q) = \begin{cases} w(s_i^p, s_j^q) & \mathrm{if } s_i^p == s_j^q \\ 0 & \mathrm{otherwise} \end{cases}\end{split}\]

With all these definitions, we can formulate the target tracking problem as a DCOP \(\langle \mathcal{A}, \mathcal{X}, \mathcal{D}, \mathcal{C}, \mu \rangle\) , where:

  • \(\mathcal{A} = \{ S_1, ... S_n \}\) is the set of sensors;

  • \(\mathcal{X} = \{ s_i^p\}, \quad S_i \in \mathcal{A}, \quad 0 \leq p \leq k\) is the set of variables, for the k sectors of these n sensors;

  • \(\mathcal{D} = \{0,...t\}\) is the domain for these variable, made of the time slots in the forecasted horizon;

  • \(\mathcal{C}\) is the set of constraints over these variables, made of constraints (1) and (2);

  • \(\mu\) is a mapping function that assign each \(s_i^p\) variable to the agent \(S_i\).

We can now use a DCOP algorithm to solve this problem in a distributed manner. Of course, the choice of the algorithm depends on the problem and the environment characteristics; given that sensors have limited cpu and memory and that the communication channel has a low bandwidth, lightweight local search algorithm like DSA and MGM are good candidates. The original article this model comes from, [ZXWW03], evaluates DSA and DBA and shows that, if controlled properly, DSA is significantly superior to DBA, finding better solutions with less computational cost and communication overhead.

Note

In order to keep this tutorial short and relatively easy to read, the model presented here is a simplified version of the model exposed in [ZXWW03]. As you may have noticed, we do not take into account the possibility for an agent to ‘sleep’ in order to save energy ; we only optimize the tracking to avoid inefficiencies. Moreover, the original model allows selecting several time slots for the same sector, which maps the target tracking problem to a multicoloring graph problem.