A high level of team situational awareness is essential during complex, largescale missions of autonomous mobile robots. When a situation appears that needs inter-agent interaction for cooperative decision-making, the basic understanding of the current conditions ought to be identical within the group. To achieve this requirement, all emergent information of acute importance must be promptly shared among team members. It is a non-trivial problem for large-sized and distributed robotic teams, especially under hard communication constraints. The problem considered in this paper is to nd an e cient emergency broadcasting strategy for search and survey operations of the robotic groups providing the fastest way for any agent to aware the remaining team in case of any unexpected changes. A number of simple ruled-based heuristics is proposed to treat the problem. The comparison between the suggested approaches is made regarding both the quality of the obtained solutions and the working speed.
The rapid evolution of the robotics technologies in recent years has led to the signi cant reliability improvement of research, military, and commercial autonomous vehicle systems. Currently, the coordinated use of autonomous mobile robot teams seems to be one of the most promising and ambitious technologies to provide an e cient solution to a range of problems, that are either too di cult or too costly to solve using traditional techniques.
However, an extensive range of fundamental problems still needs to be solved in order to
achieve high-performance cooperative teamwork in a hostile and ever-changing environment [
In this paper, we present a distributed broadcasting problem for mobile robot teams under communication constraints. The problem is to nd the shortest route for the starting aware agent to consecutively share some emergent information with the rest unaware team members, which are keeping their prescribed routes. As a rst approximation, we propose here a more abstract and simpli ed discrete model of the problem and suggest several strategies to treat it.
The remainder of the paper is organized as follows. The mathematical statement of the distributed broadcasting problem is given in the next section along with short discussion on its classi cation aspects. A number of construction heuristics to solve the problem are proposed in Section 3. Section 4 provides an in-detail description of the problem software implementation techniques, including data sets generation schemes. The results of computational experiments are explored in Section 5. The last section concludes the paper.
In general, search and survey robotic missions require a group of mobile agents to visit a set of locations inside the operational area to perform some interaction or research activities. As the operational eld is usually large compared to both sensing and manipulating capabilities of each robot, it is commonly-accepted to allocate tasks among the group to manage the job in a distributed way.
As the robots spread across the area, the current group strategy may become ine cient or
even disadvantaging due to the dynamic mission conditions. For instance, an agent may nd
the object of search in no time or become aware of some information that is crucial for mission
success [
In this situation, communication constraints become a signi cant limitation. It is a problem
for many real-world autonomous platforms, whether it is a micro-robotic swarm system with low
range communication equipment or full-scaled underwater vehicle group, which communication
abilities are limited due to the environmental properties. There is usually no all-seeing supervisor
for global broadcasting, whereas inner-vehicle communication channel could be established only
for close-enough agents [
Summarizing the above, the broadcasting problem is to nd a route for the starting agent and future informed agents to achieve the fastest data distribution among the group. As unaware group members are non-stationary and time-dependent, even if their future positions are prescribed and known, it still lays an additional layer of complexity to the routing problem.
Let the graph G = (V; E) of m vertices be a connected graph representing the operational eld. Each vertex vi, i = 1; :::; m of G is a particular location of interest, and each existent edge eij = 1 corresponds to a path between adjacent locations. For the sake of simplicity, let the graph G be unweighted, undirected, and static.
The mission is carried out by the group of n homogeneous agents (robots) a1; a2; :::; an. Each agent i travels across the graph G on a discrete-time T = fT0; T1; T2; :::g by the prescribed route Ri, which is known in advance. Route Ri = (ri0; ri1; :::; riq) is a path graph with cycles as agents may stay on the same vertex rik = rik 1 for some time doing time-consuming activities. At any point in time, any number of agents can be located within the same vertex v.
We denote the state of i-th agent at j-th time moment as a list of its current vertex and status ai(Tj ) = hvij ; sij i. The agent status sij 2 f0; 1g displays if agent i is aware (s = 1) at the time moment j. All agents are unaware at the beginning of the mission si0 = 0, i = 1; :::; n.
At some instant time moment (without loss of generality, let it be T1) random agent x became aware of some crucial information sx1 = 1. Since becoming aware, any agent receives two abilities: (i) To drop its prescribed routes to become a subject of control; (ii) To make other unaware and neighbouring (sharing the same vertex) agents aware skj = i=m1;a::x:;nfsij jvij = vkj g: (1)
The starting x-th agent has to decide if it is possible to make each other agent of the group aware in h < q time steps (h is an evaluation of the time/resource-worthy period).
Thus, the nal broadcasting problem is to nd the solution group route in the matrix form A = fai(Tj )g, i = 1; :::; n, j = 1; :::; h such that:
Each agent is unaware when the mission starts ai(T0) = hvi0; 0i, i = 1; :::; n; Unaware agents travel by their prescribed routes until becoming aware fvij = rij jsij = 0g; The random x-th agent became aware at T1, ax(T1) = hvx1; 1i;
All agents should become aware not later than h, Qin=1 sif = 1, f
As there are could be various ways to build an acceptable matrix A, those with lesser f would be preferable, minf (A).
There is also an alternate acceptance criterion to make all agents aware and gather them at some speci c vertex vR (rendezvous location) not later than h, vif = vR, i = 1; :::; n , f h. This criterion, actually, makes the problem signi cantly harder and will be considered in our future works.
Problem classi cation. As we did not nd any direct analogues of the proposed problem in
the literature, we still discovered a number of agent-based problems that share some common
features with it. Such graph models with static or mobile agents a ecting each other states
under speci c rules are often used to model the information distribution in communication and
social networks [
And the rst-hand problem of the shortest (temporally in our case) group route construction
refers to a numerous vehicle routing problem variations. Furthermore, the standard travelling
salesman problem can be represented as a subproblem of the distributed broadcasting problem,
in which unaware agents standstill on the same vertices for the whole mission and do not join
the broadcasting task after becoming aware. It follows here-from that the proposed problem is
also NP-hard. With the absence of the actual delivering process, it can be classi ed as some
kind of time-dependent multiple travelling salesman problem (mTSP). It should be noted that
the term dynamic cannot be applied here as mission conditions are still deterministic [
Among other things, one may also note, that the aware agents' behaviour is similar to one in a playground chasing game of tag, more speci cally, its team variations (so-called vampire or werewolf tag).
In this section, we propose several strategies to build the group route A providing fast data broadcasting. The matrix representation A = fai(Tj )g, i = 1; :::; n, j = 1; :::; h of the solution is apparently too big for e cient route generation straight in this form, as it contains a vast amount of both non-key and excessive information. For this reason, at rst, we have suggested using numerical vector P = fx; p1; :::; pn 1g, pi 2 f1; :::; ng, encoding the order of agent activation (becoming aware and, therefore, controllable). But, as this data structure can be interpreted in multiple ways, we have switched to a schedule form of representation.
Currently, we encode a solution as the list of agent actions in their arising sequence P = fp1; :::; p2n 1g, pi 2 f0; 1; :::; ng, pi 6= x. The requirement for the next action command arises for an unaware agent when it becomes aware and for an aware agent when it activates an unaware one (usually, both events happen simultaneously). The action command pi > 0 refers to an index of the unaware agent to be activated next by the current one, while pi = 0 means that the current agent has no one more to activate, and his broadcasting task is nished.
Two requirements should be met for the schedule P to be both feasible and acceptable: (i) Each agent (except starting agent x) should be included in the schedule P once and only once, fpi 6= pj j pi > 0 W i 6= jg, cardfpi j pi > 0g = n 1, pi 6= x. (ii) The number of 0-values ahead of any z-th element of P may never exceed the number of positive elements, prodfpi j pi = 0 W i zg prodfpi j pi > 0 W i zg, z = 1; :::; 2n 1. The second requirement ensures the permanent availability of aware agents during the broadcasting task. The matrix solution A can be easily generated from the schedule form P by replacing agent sub-routes after their activation moment with the shortest paths to the unaware agents they are commanded to activate.
Using the representation form P , we have suggested ve di erent construction heuristics to build and further compare group routes for the distributed broadcasting problem. Random order. First one is a construction heuristic that generates random vector-solution P concerning two feasibility conditions mentioned above. We consider this approach, which is a priori ine ective, not as a real solution technique but as one to compare with. Simple greedy heuristic. The second method is also a trivial, but working and reasonable in many cases, approach. In this heuristic, the action list P is built in such way, that agents are always commanded to activate the temporally nearest (as quickest to reach) unaware agent if any.
Experimental results have shown that the simple greedy approach has two observable drawbacks. Firstly, it works poorly in the situation, when several single agents are travelling diversely far away from the rest of the team. Secondly, it underperforms in areas with a vast amount of dead-ends. To answer these weaknesses, we have proposed two di erent modi cations of the greedy heuristic, which we have called Near-and-far and Smart greedy heuristic, respectively.
Near-and-far heuristic. This method has a similar greedy structure but is probabilistic. Each time an action command should be generated for an aware agent, heuristic picks either the nearest unaware agent with probability b or the farthest unaware agent with probability 1 b. The probability b is changing with time according to the balance of aware and unaware agents in the group. From the mission start, b parabolically decreases from 1 to 0:65 (experimentally de ned values) towards the time when the quarter of agents is aware. Then it returns to 1 by the moment of 50=50 ratio and stays on its level until the end of the broadcasting task. Smart greedy heuristic. Smart greedy heuristic utilizes an alternative conditional check against its simple version. It picks the nearest agent not among all still unaware agents, but among those of them, which he can reach quicker, than any other aware agent in the group. If there are no such agents at all, the current agent receives action command "0".
Branching heuristic. All previously suggested approaches have the common feature as being centralized: the starting agent generates the straight global solution A and shares it with other agents (alongside with the main broadcasting data) to abide by it. Branching heuristic is our attempt to build a decentralized broadcasting technique for the problem. The main idea here is to assign each aware agent a personal subset of unaware agents as its activation task. Each time an aware agent activates an unaware one, it divides his subset into two halves and assigns one of them to the newly activated agent. The main problem here is to build an accurate clustering rule as both spatial and temporal conditions should be considered. For this work, we use the standard single-linkage clustering with the metric being average distance in time.
The proposed problem and the heuristics suggested above have been software-implemented as the additional module for our simulation framework "Multiobjective Mission Planner" to run a series of simulation studies ( gure 1).
To start the problem solving, speci cation data can be either imported (from the main framework or speci c data le) or user-generated through the graphical interface. While generating, we represent graph vertices as a set of two-dimensional points in the plane of W H size ( gure 2a). Then we use one of two di erent methods to generate edges based on this set.
First is a standard Delaunay triangulation, in which we remove 10% of the longest edges both to create a more complex environment and to prevent fast travelling through the graph, especially by the graph borders ( gure 2b). The second method is an approach to simulate complex non-regular areas and indoor environments. To do this, we choose the neighbourhood size S = ( W H=n)1=2 and connect each pair of vertices with Euclidean distance less than S. We use parameter = 2 for big neighbourhoods and = 1 for small neighbourhoods ( gures 2c and 2d, respectively). Then we complete the graph construction by adding edges of minimal possible total length sum to provide the graph connectivity.
Up to that moment, we keep the graph in the form of the adjacency matrix. This type of representation is easy to implement, follow and modify during the graph construction stage. As soon as the nal graph state is con rmed, we convert it into the adjacency list L[i][j]; i = 1; :::; m; j = 0; :::; L[i][0] as it is much more convenient structure for path nding procedures. We keep the total number of adjacent vertices for each vertex i as 0-th element L[i][0] since it is a frequently used value.
As there are usually a large number of single runs on the same graph (di erent combinations of prescribed routes, starting agents and solution methods), we suggest building an additional distance matrix D of m m size to speed up further calculations signi cantly. To do this, we run the standard Dijkstra algorithm on each vertex i of the graph to nd a distance D[i][j] to each other vertex j.
For initial group route construction, we propose using three route generating schemes. First one is a "random agent movements", where each time-step agent either chooses to move on a random adjacent vertex or to loiter (standstill on the same vertex). The probabilities for both loitering and returning to the previously visited vertex are reduced here to prevent an agent from looping (Algorithm 1).
1 for i 1 to n do
2 R[i][0] v[i];
3 R[i][
For the second strategy, we generate single routes not as a sequence of edge movements, but as a queue of checkpoints (random vertices of G) for an agent to visit. For each consecutive pair (i; j) of checkpoints we build the shortest path of D[i][j] length to insert it to the nal route (Algorithm 2).
In the third mixed approach, route for each agent is randomly chosen to be generated by either the rst or the second strategies described above. We also have tried to implement more intelligent agent behaviour that simulates robot search activities by alternating area exploration and exploitation strategies. But, as the overall collective behaviour, in this case, wasn't so di erent from the third mixed strategy, we did not use it in the computational experiments.
The di erence between three proposed route generation methods is illustrated on the gure 3. These heat maps are constructed for the same initial data (graph G and agents set) and represent the distribution of the agents' positions while travelling by the corresponding routes for the signi cant time. As can be seen, the mixed strategy delivers more even and realistic agent distribution by combining the vertex-oriented approach of the random agent movements (focus on the strongly connected components of G) with edge-oriented features of the checkpoint heuristic (focus on the graph bottlenecks).
For the computational experiments we have generated the set of problem instances of the form "XY-m(n)". These instances are divided into nine categories: three types of graph generation schemes X=fT,B,Sg for Delaunay Triangulation, Big and Small neighbourhoods, respectively; three approaches to group route generation Y=fR,C,Mg (Random agent movements, Checkpoints queue, Mixed strategy); and we have instances of n = f25; 50; 100g agents on the graphs of m = f500; 2000; 5000; 10000g vertices for each combination of X-Y.
As solution values may strongly vary based on the initially aware agent, we use only one xed starting agent for each instance instead of the average value for combinations of di erent ones. Nonetheless, as some methods are randomness-involved, we made 100 launches for each instance and each approach to obtain both average solutions f and computational time values t.
Statistical results for a number of executed problem instances are presented in table 1. Solution time values t here are measured in milliseconds (ms) and do not include construction time to obtain distance matrix D for the corresponding graph G. A note on computation time: all calculations are running on the single core of 2.667 GHz processor of an Intel Core 2 Duo E6750 Conroe.
#
Despite the apparent advantage of the smart greedy heuristic over the rest approaches, it should be noted once more, that the solution values f presented in the table 1 are average for the series of 100 launches. Superior results of the smart greedy heuristic are provided, in the rst place, by its inability to generate low-quality solutions. For instance, both Branching and, especially, Near-and-far are able to outperform other methods on a single launch (as opposed to the simple greedy heuristic, which is always equal or worse than its smart analogue). Still they are also capable of delivering inferior solutions ( gure 4). Nonetheless, we believe that more intelligent use of these methods' features may allow them to compete with smart greedy evenly.
Another characteristic of each solution is its activation timeline. It is a function that follows the dynamic of unaware agent number with time. Figure 5 displays general outlines of activation timelines for the proposed heuristics. Weak spots of some approaches can be clearly seen here (activation speed reduction for the latest agents in 5a and 5d) as the apparent room for further improvements.
This paper presents a new problem of distributed emergency broadcasting for autonomous mobile robot teams under limited communication. The presented problem is to nd the shortest route for the starting aware agent to share some emergent information with the rest unaware members of the group and is formulated as the original variation of the vehicle routing problem. As opposed to the classical travelling salesman problem, clients (unaware robots) here are not static as they travel through the mission area along the known route on a discrete-time. The main feature of the problem is that unaware agents after being informed by any aware agent leave their prescribed routes to join the broadcasting task.
Several simple ruled-based heuristics were designed and proposed to treat the problem. A series of computational experiments and comparisons among the proposed constructive heuristics showed that the addition of even simple problem-oriented rules allows standard greedy heuristic to performs e ciently and ambitious, in terms of both solution quality and computational e ciency. Nonetheless, it is still an interesting and open problem to nd out possible ways to further improve these solutions in an e cient manner.
Among the future developments we intend to undertake, there is the development of more advanced meta-heuristic approaches and local search methods to deal with the problem. We also plan to embed more realistic environment into the problem statement, moving from the discrete formulation towards continuous time, complex weighted and directed graphs, and heterogeneous (by speed and communication capabilities) agents. Another extension of this work is to adjust the proposed constructive heuristics to the alternative problem statement with the nal rendezvous point.
This work was supported in part by the RFBF, project no. 20-07-00397 (time-dependent routing problem for distributed mobile robot teams with data sharing), and by the Russian Science Foundation, project no. 16-11-00053- (algorithm simulation framework for the dynamic multiobjective mission planning).