Suppose we need to detect the occurrence of a special event in a large area(e.g. a city). If we need that each point being visited every h hours, how could we find the optimal number of robots for cooperative surveillance?
Notice that there is no control center!
Let's say your environment is a weighted graph. The weight of each edge shows the distance. Edges ($E$) could be roads and nodes ($V$) could be junctions. Let's further assume that each robot has velocity $v$.
You say each "point" needs to be surveyed every $h$ hours. I assume that means each point in the city, which means each point in every road and junction. Since this is a city, we can also assume that the graph is connected.
As a final assumption, let's say that the junctions have zero dimension. That is a single point in the junction is taken as the graph node and the distances from the edges of the roads to that point are added to that roads weight (road length). This implies that there is no time spent in a node and all time is spent walking the edges.
First, let's find a lower bound to the number of robots. If we sum the weights of the edges, we get the total distance that needs to be travelled. The minimum number of robots required is:
$N_{min} = \bigg\lceil \dfrac{\sum_{i \in E} w_i}{h \times v} \bigg\rceil$
If it was possible for the robots to travel the edges without travelling on each road more than once, then this lower bound is the actual number required. Think of it this way. Imagine the city is like this:
X----------X
/ \
/ \
/ \
X X
\ /
\ /
\ /
X----------X
And imagine each edge is 1Km, and the speed of the robots ($v$) is 0.7Km/h. Imagine $h$ is two hours. Each robot can to travel $h \times v = 2 \times 0.7 = 1.4Km$ in that two hours. Now if you place robots at regular intervals around the loop and they all go for example clock-wise, then just as the 2 hours limit is getting expired on a point, another robot should arrive at that point. This means that the robots should be placed at 1.4Km intervals. Simply dividing the circumference of the loop by 1.4 (and taking the ceiling) gives the number of required robots.
Note: An Eulerian graph is essentially a twisted loop and for such graphs the formula above gives the exact number of required robots. Unfortunately, a city is far from an Eulerian graph.
This is a harder problem. However, here is an idea.
First, let's solve the problem for another simple case. Imagine the graph is just a line:
X--------X------------------X-------X----X-----------X
Then, the robots can't circle around anymore, but they have to "patrol". That means they have to use half of their time going one way and the other half coming back. In other words, the number of robots needed becomes:
$N_{min} = \bigg\lceil \dfrac{\sum_{i \in E} w_i}{(h/2) \times v} \bigg\rceil$
Another point of view could be robots that loop this path by going to one end and coming back to the other end in which case the number of robots would be:
$N_{min} = \bigg\lceil \dfrac{2 \times \sum_{i \in E} w_i}{h \times v} \bigg\rceil$
Which is exactly the same as patrolling the path.
That said, here is an algorithm that gives an upper bound to the number of needed robots.
1. do
2. G' = G with marked edges removed
3. if loop L exists in G'
4. put robots looping in L
5. mark edges of L
6. else
7. find a random unexpandable path P in G'
8. find the shortest path P' in G that connects both ends of P
9. create a loop L by combining P and P'
10. N1 = number of robots needed to patrol P
11. N2 = number of robots needed to loop in L
12. if N1 < N2
13. put robots patrolling P
14. mark edges of P
15. else
16. put robots looping in L
17. mark edges of L
18. while unvisited edges remain
Notes:
At 3, we try to extract out Eulerian loops out of the graph for which we know the optimal answer.
At 7, we try to get paths as long as possible out of the graph and have robots patrolling them. Make sure the path is expanded as far as possible. That is, if there is an unmarked edge connected to any end of the path, just augment the path with that edge.
The purpose for 8 and 9 is that, having robots patrolling the found path may be far from optimal. In fact, if we allow the robots to move from one end of the path to the other end via the edges that are possible already marked, then perhaps we find a loop which results in a smaller number of robots. 10 and 11 calculate the number of robots for the two possible cases and 12 decides which one was better.
Here is an example. Imagine the following graph:
X----------X
/ \
/ \
/ \
X X
\ /
\ /
\ /
X----------X
/ \
/ \
/ \
X X
\ /
\ /
\ /
X----------X
First, we find a loop and mark it. Imagine this is the top loop:
X**********X
* *
* *
* *
X X
* *
* *
* *
X**********X
/ \
/ \
/ \
X X
\ /
\ /
\ /
X----------X
Now we are left with this path:
X X
/ \
/ \
/ \
X X
\ /
\ /
\ /
X----------X
We can either patrol the path with a larger number of robots, or make a loop with an edge previously visited and have fewer robots travelling it. In the end, two loops is better.
The algorithm could have also found a different solution. For example, the first loop could have been the outer loop:
X**********X
* *
* *
* *
X X
* *
* *
* *
X----------X
* *
* *
* *
X X
* *
* *
* *
X**********X
After which we are left with the center edge as a path:
X----------X
And obviously, it's better to have robot(s) patrolling it than to create a very large loop out of the visited edges.
It is interesting to note that in this case, the shortest path P' as in the algorithm above is in fact this path itself. As a result, the loop is essentially robots that loop between the ends of this path (rather than patrolling only their specific portion of the path). The optimal number of robots in either way is the same as mentioned before.
I really don't know. It is possible (but I haven't proven anything) that this problem doesn't even belong to $P$, so there may not be any useful solution for it at all (again, I may be wrong).
If you find that the "Upper Bound" algorithm doesn't provide small enough number of robots, for example by examining the graph yourself and find obvious optimizations, you could also always try optimization algorithms (such as genetic algorithms).
Notice that there is no control center!
Mind you, my solution is to calculate the paths each robot needs to circle in (or patrol) offline and then program the robots to keep to their path forever. This doesn't address problems such as a robot breaking and others having to cover for it for example.
