The problem considered in this paper is to produce both routes and refuelling schedules for a heterogeneous eet of autonomous mobile vehicles that provide e cient group work performance in large-scale persistent monitoring missions. In the model, the route for the group of vehicles must be determined on the extended time period to ensure regular and well-timed inspections of a set of tasks at scheduled intervals. The routes are limited by the speed limitation, onboard equipment and fuel capacity of the vehicles alongside with visitation frequency and equipment requirements of each task. Fuel capacity limitations force vehicles to recharge (refuel) at intervals using charging stations within the operation area. It is a problem of considerable practical interest to e ectively route the heterogeneous group of vehicles under continuous rotation and in a dynamic environment with vehicle systems being subjected to malfunctions and unforeseen events. We propose two-level architecture for the group control system to coordinate cooperative vehicle actions during long-term multi-objective missions: while the high-level planner is designed to dynamically adjust fail-safe refuelling schedules for the vehicles in the group, the low-level planner is aimed to the accurate generation of the local group routes ensuring well-timed accomplishment of all tasks under technical constraints.
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. This has encouraged new trends in environmental robotics science relating to robot and sensor network interaction, model-aided path planning, adaptive sampling, and cooperative robotic teams. In situations when it is required to establish a sampling network within the certain region in short order (militaristic operations, natural disasters, etc.), using a team of autonomous mobile robots (AMR) allows organizing an e cient large-scale environmental monitoring of areas of interest.
However, a large range of fundamental problems needs to be solved in order to achieve
highperformance cooperative teamwork in a hostile and ever-changing environment [
In general, the mission-planning problem for the environmental monitoring is a variation of
vehicle routing problem (VRP) under speci c spatio-temporal constraints: a set of di erent tasks
should be feasibly allocated between vehicles of the group in the most e cient visitation order.
In the context of persistent monitoring, when the robot team is deployed in an environment over
a sustained period of time, mission tasks usually require not the single visitation but the series
of periodic inspections by AMRs with a given frequency [
A signi cant limitation in the aspect of long-term planning is the periodic refuelling necessity
due to the limited AMRs battery capacity [
In general, persistent monitoring missions require a group of vehicles to visit and inspect (perform some research activities) the set of tasks at scheduled intervals on an extended time period and under operational requirements. The routing problem here is to nd a feasible group route ensuring, as far as possible, the well-timed inspection of the majority of tasks under continuous change of currently working team due to the robots recharging needs. The problem parameters are de ned as follows below.
We denote by T the whole mission length and suppose that it is a big value in the context of global mission planning. Assume there is a set of tasks N = f1; :::; ng distributed over a speci c operational area. These tasks are de ned not only by their location in space but also with the demanded periodicity of inspections pi and the single-inspection duration time si, i 2 N , which all are known in advance. On top of that, a speci c type of research equipment ei 2 f1; 2; :::; lg, i 2 N is required for the inspection of each task.
The periodicity value pi de nes the demanded duration of the time interval between two successive inspections of i-th task by robots of the group. Hence, in case of arrival ahead of time, AMRs should loiter until the expiration of the required interval pi, and, in case of delayed inspection, new period pi for the i-th task will start not from the expected, but from the actual inspection time.
The group of robots performing the mission consists of m vehicles, which may di er by their cruising speed vk, battery capacity bk, battery level b(t)ck bk and set of onboard equipment djk 2 f0; 1g, j = 1; :::; l, k = 1; :::; m, where l is the number of all types of research equipment. Battery limitations force AMRs to refuel at intervals by docking to the specialized charging stations. Concrete locations of these are not essential since we only need the estimated travelling time for each robot to get to the nearest free recharging dock from the operation area. We denote the average charging speed for all charging stations by constant parameter c 1. In that case, full charging time for empty battery with a capacity of b hours would be b=c hours. Here we rate batteries not in energy units but as average run-time on cruising speed. We assume that the number of stations/docking spaces is not limited so that there is always a free dock for a vehicle in need. Additionally, we assume that each type of equipment is installed on at least two di erent vehicles. This assumption allows the group to send any single robot to a recharging station without losing the performance capability of the remaining team.
The process of persistent monitoring mission implementation in the statement proposed above is schematically shown in the gure 1. At the depicted time point, the currently working team consists of two unmanned vehicles; one more vehicle has recently left the group and now is travelling to the charging station for refuelling; the fourth vehicle has already been refuelled and now it is on its way to re-join the working team at the speci ed rendezvous location.
It is worthy of note that the multi-vehicle system should be self-controlled with no human operator or another external supervisor involved. Thus, all parallelizable calculations should be distributed among robots to achieve both maximal processing power and decentralized control hierarchy. In order to achieve proper decentralization, robots in the squad should coordinate in a way to periodically establish group communication sessions for inner-vehicle data transferring. As the real communication channels are typically slow and limited in range, we assume that communication sessions could be established only during so-called rendezvous, when all accessible AMRs simultaneously arrive at the speci ed location.
The requirement for periodic communication sessions primarily arises due to the dynamic nature of real-world missions when both the working group and set of tasks could be subjected to unexpected changes. These changes may occur in real-time, making it necessary to adjust the current plan in order to maximize the group e ciency in new conditions. Among the events that require re-planning are: adding new tasks or withdrawing the old ones; change of tasks parameters; unexpected AMR loss or malfunction; collecting new AMR of previously lost one; AMR leaving the group for recharging; collecting recently recharged AMR.
The e ectiveness of the group as a whole is de ned by maintaining the regularity of welltimed inspections of all tasks. Situations of vehicles arriving too late and delaying the inspection are undesirable and should be excluded, if possible. Thus, our objective is to develop the synchronous control architecture able to construct and adjust group routes providing: minimum inspection delays during continuous persistent monitoring; e ective management of AMRs refuelling process; regular communications sessions within the group.
The proposed problem combines features of a number of well-known group routing problems,
all of which are NP-hard: coverage and patrol routing problem, multiple travelling salesman
problem (mTSP) and several variations of the classical vehicle routing problems (VRP). The
formulation of the vehicle routing problem and some methods for its solution were rst proposed
in [
In coverage and patrol problem a group of agents should continuously revisit a set of waypoints
within a given area in order to maximize the visit frequency for each waypoint [
The nature of the persistent visitation problem presented in [
The problem of persistent visitation shares a lot of features with the persistent monitoring
problem proposed in this work. At the same time, there are signi cant di erences between two
problems that do not allow us either to classify them as variations of the same problem nor to use
identical methods and ideas to solve them. The main di erence here is the target service-time
requirements: while in [
In the scienti c literature, there is a large number of works that explore di erent extensions
of the persistent visitation model. However, the overwhelming majority of them are devoted
to constructing cyclical trajectories of limited length. Restrictions of the hard type do not
allow such mission decomposition, which leads us to the acyclic routes with a oating planning
horizon [
E ective mission planning for real-world robotic operations is a complicated and challenging
problem, especially when it is required to respond to environmental changes and unexpected
events. While even in static and fully known environment group routing alone is a problem
of high computational complexity, dynamic conditions drastically devalue the requirement
for an optimal solution [
According to this scheme, each decomposition point triggers a rendezvous of the currently working AMRs for the purpose of both communication and vehicle rotation activities due to the refuelling needs (sending robots to the recharging station or collecting recently recharged vehicles back to the group). As the rejuvenated group continues the task's inspection until the next decomposition point, each vehicle in the group computes to nd the best group route for the next operating period considering the upcoming group rearrangement: which AMRs would leave the group during next rendezvous and which would rejoin. Such a pre-planning would allow for saving time and shortening the rendezvous length alongside with calculations distribution among vehicles. In such an instance, inner-vehicle communication at the end of each operating period should include the exchange of the AMR's best-found solutions ( gure 3).
Consequently, the upper-level mission planner strategy is to manage operating periods by
scheduling AMRs recharging cycles. A mission planner should be simple, fast and reliable,
as quick and e ective re-planning is required each time an unexpected event occurs. On the
other hand, the lower-level route planner is not designed to react to environmental dynamic
changes. However, as the operating eld is split via decomposition to the smaller spaces, the
routing system should be capable of high-performance local group motion planning under
spatiotemporal constraints. The routing problem here is to achieve the well-timed task's inspection
for the group of functionally heterogeneous robots and to ensure simultaneous group arrival
at the rendezvous location by the end of the operating period. Task allocation problem on a
single operating period should not be treated separately from the global objective as successive
operating periods share common terminal conditions. As both global mission planning and local
route planning are essential for monitoring e ciency, proper cooperation and synchronization
between both levels would allow the control system to deal with complex requirements and
restrictions, which are aimed at the more accurate simulation of real-world problems [
Summarizing the above, the high-level mission planner is to construct an appropriate group rotation schedule providing reliability and high-performance capability of the working group. As mission length T is supposed to be a considerable big value, we suggest using search space discretization to speed up both encoding and nding the solutions. For that reason, we will consider mission time T as a sequence of equal time intervals T = T 1; :::; T z , z = T =T0, where T0 is the duration of each interval. In this representation, the working schedule of a single robot can be denoted by a binary z-dimensional vector, where each attribute h stands for a robot's status during the corresponding time interval (h = 0 if the vehicle is currently working and h = 1 otherwise). A schedule of the i-th vehicle is considered as feasible if none working period (continuous sequence of x 0-attributes) lasts longer than the vehicle's battery level at the beginning of that period x T0 b(tx)ic. The group schedule at this point can be represented as z-by-m binary matrix H = fhij g as shown in the gure 4.
As AMRs are not obliged either to leave the group only being completely discharged nor to always recharge up to the entire full battery (although it is preferable), we can adjust charging periods for each robot during the mission in order to obtain the desirable group rotation schedule: (1) The rst and the main requirement is to maintain robots in the group in good working order by organizing well-timed recharging for all vehicles in need. (2) Secondly, the working group should always be functionally able to inspect each mission task by having access to all available types of onboard equipment. (3) Then, we want to exclude as far as possible the simultaneous mass charging of several robots since it reduces the performance capability of the remaining group. (4) Finally, since each rendezvous distracts robots from the task's inspection, we want to exclude excessive rendezvous where possible. In order to do this, we want to conjoin closely-spaced rendezvous together by shifting them to the common time-point.
We regard the rst requirement from the list above as a feasibility criterion and the next three as e ciency criteria for the planning problem. Thus, we propose using a convolution of two di erent functions as the global objective function here:
f (H) = fG(H) + z fR(H) ! min
The rst function fG(H) 2 [0; z] evaluates given schedule H in respect of the group performance capability during the mission progress, while the second one fR(H) 2 [0; 1] keeps track of the rendezvous frequency. The loss function (2) evaluates the performance capability of absent robots on each interval T i of the mission by using three di erent multiplier factors responsible for the number, speed of recharging robots and equipment availability, respectively: z m fG(H) = X((X hij ) ( i=1 j=1
Pjm=1 hij vj
Pjm=1 vj ) (1
l Y (1 k=1
j Pjm=1 hijjdk )))
Pjm=1 dk (1) (2)
On each time period T i function (2) takes the value on the interval [0; 1]. More speci cally, 0value means that all robots are currently working in the group and 1-value stands for undesirable situations when all carriers of the particular equipment are currently recharging.
The second objective function estimates the number FE (H) of expected rendezvous (time intervals, where at least one vehicle is changing its status) and compares it to the minimum possible number of rendezvous FI (H): fR(H) =
FE (H) FI (H)
FE (H)
z ; FE (H) = X(1 i=2 m m Y (1 jhij hi 1j j))); FI (H) = m T = X(bj =c) (3) j=1 j=1
Since function (3) always takes the value on the interval [0; 1], we use weighting factor z in the objective function (1). Thus, the planning problem is to nd such feasible schedules, which would satisfy objective function (1) the most. The feasibility of a schedule as a whole cannot be determined in the explicit form and so it should be checked additionally via specialized algorithmic procedure considering such AMR's parameters as speed, battery level, and capacity alongside with travelling time to reach the nearest charging station and, nally, charging rate.
In general, the scheduling problem is NP-complete, and therefore the use of heuristic methods
to solve it seems the most reasonable. Thus, we propose using a simple modi cation of genetic
algorithm (GA) since GA o er near-optimal solutions in a faster time and with better scalability
at average than other heuristic and meta-heuristic approaches [
To decrease the problem size we use a compressed vector representation of the matrix-schedule H as the chromosome ( gure 5) with function (1) as the objective function. To de ne the chromosome's tness, the matrix form of the solution should be restored at rst by specialized repairing procedure that combines solution decoding with intelligent local optimization to decrease the number of possible rendezvous. For the genetic operators, we suggest using random mutation with both two-point and PPOX-crossovers as they are widely recognized to be the most e cient genetic operators for a variety of scheduling problems.
High-level mission decomposition allows us to eliminate refuelling aspect of the problem and neutralize the ever-changing group composition challenge for the route planning problem. Besides, it leads to the problem space reduction, which is another advantage of the proposed approach. The routing problem on a single operating period is formulated as stated above in Section 2. Status of each object of the mission is inherited from the previous operating period, a subset of k m currently working robots is located within the rendezvous area and each vehicle is guaranteed to have enough battery level to work through the whole operating period.
Let us denote by r the route of a single robot as a list of task numbers in the consecutive order of their planned visits:
r = hV0; V1r; V2r; :::; Vur; V0:i
As can be seen, vehicles start each period from the rendezvous point V0 and travel back there at the end of the period to take part in group rendezvous. It also should be noted that any task could be included more than once into the route of a single robot. The group route is a set of all single AMRs routes (4):
R = fr1; :::; rkg: The routing problem is to generate feasible group route (5) providing: regular and well-timed inspections of all tasks; on-time arrival of all vehicles to the rendezvous location; serviceable mission conditions at the end of the operating period (no tasks with expired or near-expired inspections).
To measure the quality factor of di erent group routes in terms of given requirements, we
propose a scenario-based approach that relies on the list of desirable and undesirable both
singlerobot and group behaviours. Each scenario includes a priority-order value, set of triggering
events, scoring type (penalty or reward) and scoring conditions. Trigger events of all scenarios
are checked via the simulation run of the group work with the output being a sum of reward
and penalty points weighted according to given priorities. For scaling and normalizing points
charged by di erent events, we use an original scoring technique presented in our earlier works.
This technique introduces an additional hotness function aik(t) evaluating the relevance of each
task inspection by a given robot at any moment of time. Hotness function is constructed in
such a way, that in the case when the group is unable to inspect all tasks without any delays,
well-timed inspections would be assured for tasks with lesser periodicity, which are likely to be
more important. Further particular details of the normalizing procedure can be found in [
Turning back to the routing problem studied in this work, we suggest using the next four scenarios presented in table 1.
Each time vehicle visits a task Each time vehicle starts inspection Group arrives at the rendezvous location Group arrives at the rendezvous location
Inspection is delayed Bad future conditions Timely disunited arrival (4) (5)
The lower-level route planning problem is a much more complicated and computationally intensive problem as it is known to be NP-hard. Thus, there are no algorithms solving it in polynomial time, which leads us to the class of approximation algorithms which allow obtaining rational sub-optimal solutions in low computational time. Over the past decade, heuristic and meta-heuristic approaches for solving the routing problems have been rapidly developing. So far, the most e cient methods apply decomposition schemes, intelligent neighbourhood search strategies and components of exact optimization methods. Newly designed heuristics also became more exible and versatile as they could be applied to a wide range of VRP variations without any structural changes.
Among others, evolutionary methods have proven to be highly successful both on a classical
VRP and on a number of its variations [
Both mission- and route- planning algorithms are implemented in our simulation framework "Multiobjective Mission Planner" to run a series of simulation studies. The high e ciency of the suggested approach is shown through these tests. Upper-level mission planner is proved to be fast, accurate and reliable as it allows fast construction of group schedules within the 3% of the optimal value ( gure 6). Lower-level routing system ( gure 7), in return, o ers e cient near-optimal ( 1%) task allocation procedure even under strict constraints and the large-sized search eld. The proposed cooperation scheme between both planners allows the group to be e cient under continuous squad rotation due to the recharging needs.
This paper presents a two-level approach to the AMRs persistent routing problem that incorporates rendezvous point-selection scheme providing advantageous mission decomposition and local task allocation scheme to coordinate currently available heterogeneous vehicles in the most e cient way. The next stage of this work involves a wide diversity of mission tasks: ones that couldn't be inspected by a single robot, tasks with inspection time relying on the number of inspecting vehicles, prolonged and areal task's positions, etc. Another extension of this work is to develop a real-time path planner to deal with complex and unfamiliar environments, collision avoidance and dynamic obstacles, as an additional, third level of the group control system.
This work was supported by the Russian Science Foundation, project no. 16-11-00053- . This work was also supported in part by the Presidium RAS, program no. 7, project "Methods, algorithms and tools for the decentralized group solving of problems in computing and control systems" (reg. no. AAAA-A18-118031590006-2).