Modeling problems as DCOPs

What we have seen so far in previous tutorials may seem 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 its DCOP algorithms can be used for real applications.

As a topic in the Multi-Agent Systems field, DCOPs 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 as 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 sensors 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 which area it operates on.

In an open environment, sensors used in tracking systems usually run on batteries, which means they must use as little energy as possible, in order to increase the system operation’s lifetime. This includes switching themselves off whenever possible, without degrading the system’s detection performance.

These sensors are also lightweight devices with limited memory and computation capability. They communicate with each other through radio signals, which may not be reliable. Each sensor can only communicate 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 which sector the sensor will scan. These agents coordinate in order to plan an efficient scanning strategy ; this problem is actually a distributed planning problem.

Let \(S = \{ S_1, ... S_n \}\) be the set of n sensors. Each agent \(S_i\) can select the area to scan from 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 its \(s_i^j\) sectors or sleep.

The \(s_i^k\) are our decision variables, whose value represent 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 having more than one sensor scanning the same sector simultaneously. 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}\]

Using 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, by Weixiong Zhang, et al. [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.