Coverage control with occupancy grid based target detection and tracking


alt="Your browser understands the < APPLET > tag but isn't running the applet, for some reason. " Your browser is completely ignoring the < APPLET > tag!

Examples of mission spaces

Just copy (Ctrl-c) and paste (Ctrl-v) the numbers between two "star" lines into the input box below the "Update Obstacles Listing Below" button and hit that button to apply:

**********************************************

5 -1 5 20 7 20 7 -1
15 -1 15 20 17 20 17 -1
25 -1 25 20 27 20 27 -1
35 -1 35 20 37 20 37 -1
45 -1 45 20 47 20 47 -1
7 26 7 51 8 51 8 26
27 26 27 51 28 51 28 26
47 26 47 51 48 51 48 26
57 26 57 51 58 51 58 26

*********************************************

7.5 7.5 2.5 12.5 7.5 17.5 12.5 12.5
7.5 20 2.5 25 7.5 30 12.5 25
7.5 32.5 2.5 37.5 7.5 42.5 12.5 37.5
22.5 7.5 17.5 12.5 22.5 17.5 27.5 12.5
22.5 20 17.5 25 22.5 30 27.5 25
22.5 32.5 17.5 37.5 22.5 42.5 27.5 37.5
32.5 7.5 32.5 17.5 42.5 17.5 42.5 7.5
32.5 20 32.5 30 42.5 30 42.5 20
32.5 32.5 32.5 42.5 42.5 42.5 42.5 32.5
47.5 7.5 47.5 17.5 57.5 17.5 57.5 7.5
47.5 20 47.5 30 57.5 30 57.5 20
47.5 32.5 47.5 42.5 57.5 42.5 57.5 32.5

*********************************************

17 15 17 35 43 35 43 15
28 -0.1 28 14 32 14 32 -0.1
28 40 28 50.1 32 50.1 32 40
-0.1 23 -0.1 27 10 27 10 23
44 23 44 27 60.1 27 60.1 23

******************************************

5 5 5 20 7 20 7 5
4 30 4 32 20 32 20 30
15 10 15 12 26 12 26 10
40 8 40 20 50 20 50 8
32 35 32 47 35 47 35 35
36 32 36 34 52 34 52 32

******************************************

9 -0.1 9 41 11 41 11 -0.1
11 39 11 41 51 41 51 39
49 9 49 39 51 39 51 9
19 9 19 11 51 11 51 9
19 9 19 31 21 31 21 9
19 29 19 31 41 31 41 29
39 19 39 31 41 31 41 19
29 19 29 21 41 21 41 19

*********************************************

Detailed instructions (Under construction):

Welcome to this demo page. Here you can create your own mission scenario, adjust many parameters of the algorithm and see the response of the mobile sensor nodes in real-time. After the applet is loaded, it will populate the bounded mission space with several obstacles and sensor nodes.

The table in the upper-right corner shows the location and heading of each node. In lower-right, you can find several lines of numbers listed in a text area under a button labeled Update Obstacles Listing Below. Each line in that text area represents the vertices locations (x coordinate followed by y coordinate) of one polygonal obstacle in the mission space. If you want to change the configuration of the obstacles, you can modify the content of that text area and click the big button above it to update the mission space. IMPORTANT: Each line should describe a convex obstacle. You can create any nonconvex polygonal shape by combining two or more convex polygons. In addition, two obstacles should not share a vertex. (They can have vertices which are very close, but not exactly the same)

After creating a complicated mission space, you can copy the content of the text area to a text file for future use. There are some mission space samples listed at the end of this page. You can copy and paste them into the text area.

Selecting the checkbox Evaluate Objective Function will make the applet evaluate the objective function. The mission space is color-coded to illustrate the detection probability: events in the magenta area are detected with probability greater than 0.97; the area with color graduating from cyan to green corresponds to a detection probability in the range [0.5, 0.97]; and the area with color graduating from white to yellow corresponds to a detection probability in the range [0, 0.5]. The white area can be essentially considered as blind spot.

The Resolution drop-down list allows you to change the resolution of objective function evaluation. Thus you can trade details for frame rate.

On the right side of the Real Time Control check box, you can find some simulation parameters for tweaking.

You can specify the number of nodes you want, up to 25.

(Note that to change the parameters introduced later requires the user to press the ENTER key while the insertion point is still in the modified text box.)

Integration Resolution is the resolution of numerical integration in coverage control algorithm. Make it bigger if you feel the applet is running too slow.

Max Speed can be considered as the step size in the gradient algorithm. A high value at the beginning can help avoid local optimum near initial state. The final oscillation can be reduced by decreasing this parameter, e.g., to 1 or 2.

Sensing Decay indicates the sensing capability of the sensor nodes. A smaller decay means the sensor can sense effectively farther away. If it is zero, then the sensor becomes line-of-sight type, as in the classic Art Gallery Problem setting.

Sensor nodes will ignore any event outside of their Sensing Range, even the event's detection probability is nonzero. This parameter is usually kept to its default value unless you really want higher frame rate.

Max Norm determines how the node's speed slows down when it approaches a smooth local optimum. However, since the objective function is generally nonsmooth, oscillation can not be avoided with a constant stepsize. To see how it works, click here.

The Low Detection Boost box at the top is used to achieve a balanced coverage. It gives area in the mission space with under 0.5 detection probability more weight during the gradient calculation. If both numbers are set to 1, then it has no effect. After the system converges, you may want to change them to large values to see how it works. The nodes will tend to eliminate more under-covered yellow or white area than usual. The first number is for area with detection probability of 0.1 to 0.4. The second is for area with lower than 0.1 detection probability.

Estimate Initial Positions is an experimental feature which gives an approximation of where the nodes should be allocated. The value indicates the relative importance of that location. The algorithm is motivated by the calculation of gravitational force.

There are two ways to interact with the nodes: You can press the Left mouse button on a node and do drag-and-drop. You can pause the simulation so the nodes are easier to catch. If your mouse has a wheel button, click it will pause/continue the simulation.

The easier way to catch nodes when they are moving is to press your mouse and drag a rectangle from upper-left to lower-right. Every node inside the rectangle when you release the mouse will change color and become "selected". Click the Right mouse button anywhere in the map will teleport the selected nodes to that point.

When the simulation is not paused, it is highly recommended to turn off Evaluate Objective Function before interacting with the nodes using your mouse. But when the simulation is paused, I found it very useful to turn on Evaluate Objective Function and manually assign the locations of nodes to see how the coverage changes with a small perturbation of the node position.