Keywords

1 Introduction

Modern technologies have brought new perspectives and trends both in the military and civil domains in the last decades. Unmanned robotic systems have been used in military operations as well as in many civil applications. For example, Unmanned Aerial Systems (UASs) have been used in applications such as monitoring and inspection [1, 2], mapping [3], communication and networking [4], traffic monitoring [5], construction [6], and many others.

In the military, the trend is to use the robotic vehicles in connection with the decision support systems for tasks such as monitoring, reconnaissance, surveillance, searching for target objects, etc. These systems plan the operation in support of a commander. The goal is to plan and execute the operation optimally according to the selected optimization criterion. For example, these systems can plan the reconnaissance operation to explore the area of interest as fast as possible with UASs that are available.

At the University of Defence, the Tactical Decision Support System (TDSS) is being developed for the tactical level commanders of the Czech Army as a part of the Command, Control, Communication, Computer, Intelligence, Surveillance, and Reconnaissance (C4ISR) system. The main goal is to support commanders on the tactical level with their decision-making process.

The TDSS consists of many models of military tactics. The commander can use one of the models to plan his/her task, if the model and the task are mutually compatible. The plan respects the current tactical situation and requirements, and provides the possible variants to fulfil the task along with the second-order effects [7]. The models implemented in the TDSS are e.g. models for planning logistics on the battlefield, planning reconnaissance or surveillance operations using multiple unmanned aerial or ground vehicles [8], at many others. More information about this topic is covered in [9,10,11,12,13,14,15,16,17,18,19,20,21,22].

This article deals with one of the models of the TDSS: Deployment of Observation Posts in the Area of Operations (DOPAO). The goal of this model is to plan the location(s) of observation post(s) in order to observe as large area of interest as possible while the key tactical requirements need to be met.

The paper is organized as follows. Section 2 presents the mathematical model. In Sect. 3, the problem solution is proposed based on the stochastic principles. Section 4 presents the model implementation in the TDSS. Section 5 shows the benchmark problems designed to verify the proposed solution. Finally, Sect. 6 concludes the paper and presents the future work of the authors.

2 Problem Formulation

Let \( A_{I} \subset A \) be the area of interest to be observed as a part of the area of operations. This area is represented by a polygon with or without holes. Every point laying in the area of operations is defined by its elevation, which is altitude above the sea level. In the area, there may be a number of non-transparent objects and obstacles of some height. The uneven terrain and/or obstacles may occlude some portion of the area when observed from a static position.

Let \( O = \left\{ {O_{1} ,O_{2} , \ldots ,O_{N} } \right\} \) be a finite set of observation posts to be deployed in the area of operations where \( N \ge 1 \) is their number. From each observation post \( O_{i} \in O \), a portion of the area of interest \( A_{i} \subseteq A_{I} \) is observed. Every point, laying inside the area of interest with a visual line of sight (VLOS) between the observation post and this point, is marked as visible; otherwise it is marked as occluded. The total portion (coverage) of the area of interest, that is observed from at least one of the observation posts, is determined according to formula (1).

$$ A_{O} = \bigcup\nolimits_{i = 1}^{N} {A_{i} } \quad {\text{for}}\;{\text{all}}\;O_{i} \in O $$
(1)

where

\( A_{O} \) :

is the area of interest observed from all posts,

\( A_{i} \) :

is the area of interest observed from post \( O_{i} \in O \),

\( N \) :

is the number of observation posts deployed

Each observation post \( O_{i} \in O \) is defined by the parameters as follows:

  • Height of observer: the height above the terrain from which the area of interest is monitored.

  • Height of target objects: minimum height of target objects inside the area of interest to be observed. Lower objects may not be detected.

  • Visibility range: maximum range in which objects can be detected. It is a distance between the observation post and farthest point where objects can still be detected.

The principle of determining visibility from observation posts to points inside the area of interest is shown in a plane in Fig. 1. There is a cross-section of terrain, an observation post is placed on the left, an object to be observed located inside the area of interest on the right. The minimal object height may determine whether or not the object is visible from the observation post: object ② is visible, whereas object ① is not.

Fig. 1.
figure 1

Visibility from an observation post in a plane

Full size image

Figure 2 presents the plan view of an example situation. There are two observation posts, the area of interest is bounded by a polygon of blue color. Green area is the total area observed from both posts (\( A_{O} = A_{1} \cup A_{2} \)), red area is occluded.

Fig. 2.
figure 2

Coverage of the area of interest (Color figure online)

Full size image

Let \( S \in A \) be a position of a superordinate unit in the area of operations. Let \( C = \left\{ {C_{1} ,C_{2} , \ldots } \right\} \) be an infinite set of all points in the area of operations which can provide shelter for observation posts, typically edges of forest, vegetation or terrain obstacles. Let \( R = \left\{ {R_{1} ,R_{2} , \ldots } \right\} \) be an infinite set of points in the area of operations which constitute possible escape routes.

Let \( Eny = \left\{ {Eny_{1} ,Eny_{2} , \ldots ,Eny_{M} } \right\} \) be a finite set of enemy units deployed in the area of operations where \( M \ge 0 \) is their number. Enemy units observe some portion of the area of operations based on their locations and parameters, which are the same as in case of observation posts (height of observer, height of objects, visibility range). The area observed by the enemy \( A_{Eny} \subseteq A \) is a set of all points to which at least one enemy units has the VLOS – see formula (2)

$$ A_{Eny} = \bigcup\nolimits_{i = 1}^{M} {A_{Eny\,i} } \quad {\text{for}}\;{\text{all}}\;Eny_{i} \in Eny $$
(2)

where

\( A_{Eny} \) :

is the area observed by all enemy units,

\( A_{Eny i} \) :

is the area of interest observed by enemy unit \( Eny_{i} \in E \),

\( M \) :

is the number of enemy units deployed in the area of operations

The locations of observation posts are not known at the beginning. The objective of the DOPAO model is to maximize the portion of the area of interest observed from all posts according to formula (3).

$$ maximize\left( {\left| {A_{O} } \right|} \right) $$
(3)
where \( \left| {A_{O} } \right| \):

is the size of the area of interest observed from all observation posts

There are some tactical requirements on observation posts limiting their possible locations in the area of operations. Basic requirements can be formulated as follows:

  • Connection with the superordinate unit.

  • Hidden establishing and abandoning the post, hidden observation process.

  • Proximity of the escape route in case of emergency leave.

  • Minimization of probability of disclosure by the enemy.

Individual requirements are ensured by the following principles (all constraints are optional):

  • Posts must be placed within same maximum distance from the superordinate unit to ensure the communication – see constraint (4).

  • Posts must be placed near an edge of forest, vegetation or some other terrain obstacles to ensure the hidden observation process – see constraint (5).

  • Posts must be placed in some proximity of an escape route (road) to be able to leave in emergency – see constraint (6).

  • Posts must not to be placed in the area observed by the enemy – see constraint (7).

  • Posts must be placed outside the area of interest – see constraint (8).

$$ \left| {O_{i} - S} \right| \le D_{comm} \quad {\text{for}}\;{\text{all}}\;O_{i} \in O $$
(4)
$$ \hbox{min} \left( {\left| {O_{i} - C_{1} } \right|,\left| {O_{i} - C_{2} } \right|, \ldots } \right) \le D_{shelter} \quad {\text{for}}\;{\text{all}}\;O_{i} \in O\;{\text{and}}\;C_{j} \in C $$
(5)
$$ \hbox{min} \left( {\left| {O_{i} - R_{1} } \right|,\left| {O_{i} - R_{2} } \right|, \ldots } \right) \le D_{escape} \quad {\text{for}}\;{\text{all}}\;O_{i} \in O\;{\text{and}}\;R_{j} \in R $$
(6)
$$ O_{i} \notin A_{Eny} \quad {\text{for}}\;{\text{all}}\;O_{i} \in O $$
(7)
$$ O_{i} \notin A_{I} \quad {\text{for}}\;{\text{all}}\;O_{i} \in O $$
(8)

where

\( O_{i} \in O \) :

is an observation post to be deployed,

\( S \) :

is the superordinate unit deployed in the area of operations,

\( D_{comm} \) :

is the maximum allowed distance between posts and superordinate,

\( C_{j} \in C \) :

is a point which can provide a shelter for observation posts \( O_{i} \in O \),

\( D_{shelter} \) :

is the maximum allowed distance between posts and a shelter,

\( R_{j} \in R \) :

is a point constituting a possible escape route to leave post \( O_{i} \in O \),

\( D_{espace} \) :

is the maximum allowed distance between posts and an escape route,

\( A_{Eny} \) :

is the area observed by enemy units,

\( A_{I} \) :

is the area of interest

3 Problem Solution

A stochastic algorithm based on the simulated annealing principles has been proposed to solution of the problem formulated in the previous section. A solution to the problem is represented by a vector of \( 2N \) independent variables where \( N \) is the number of observation posts to be positioned: \( X = \left\{ {x_{1} ,y_{1} ,x_{2} ,y_{2} , \ldots ,x_{N} ,y_{N} } \right\} \), i.e. a position of each observation post \( O_{i} \in O \) is given by two-dimensional coordinate \( x_{i} \), \( y_{i} \).

The algorithm in pseudocode is shown in Fig. 3. The key parameter of the algorithm is temperature \( T \). Solution \( X \) is processed in successive loops (points 3 to 16), which differ by the value of temperature; the temperature is lowered from one loop to another until it reaches its minimum value \( T_{min} \) (which is a termination condition of the algorithm).

In each loop, a number of steps are repeated (points 5 to 15). The key process is the transformation of solution \( X \) to solution \( X^{{\prime }} \) (point 6). This transformation consists in changing the value of:

  • One randomly selected variable in solution \( X \).

  • All variables in solution \( X \).

  • Variables in solution \( X \) selected randomly with probability \( p_{trasform} \).

Which option will be used depends of the setting. The selected variable(s) is(are) changed based on the current value of temperature \( T \). In general, the higher the temperature, the bigger the change. Thus, at the beginning of the algorithm, the variable may be changed in its full domain, where towards the end of the optimization, only small changes are made. It has an effect of searching the full state space at the beginning, and tuning the solution at the end. The changes are made by a random number generator with the Gaussian distribution.

Fig. 3.
figure 3

Optimization algorithm

Full size image

It the transformed solution \( X^{{\prime }} \) is feasible (point 7), i.e. it meets all selected requirements expressed by formulae (4) to (8), the new coverage of the area of interest \( A_{O}^{{\prime }} \) is calculated and the original solution is replaced by the transformed solution (point 10) with the probability given by the Metropolis criterion (point 8) in formula (9). This criterion states that if the original solution is worse (it has smaller coverage), it is always replaced, otherwise it is replaced with the probability depending on the difference between both solutions and the current temperature. This principle helps the solution not to be stuck in a local optimum.

$$ p\left( {X \to X^{{\prime }} } \right) = \begin{array}{*{20}c} {\left\{ { \begin{array}{*{20}l} 1 \hfill \\ {e^{{ - \frac{{\left| {{\text{A}}_{O} } \right| - \left| {A_{O}^{{\prime }} } \right|}}{T}}} } \hfill \\ \end{array} } \right.} & {\begin{array}{*{20}l} {{\text{for}}\;\left| {A_{O}^{{\prime }} } \right| \ge \left| {{\text{A}}_{O} } \right|} \hfill \\ {\text{otherwise}} \hfill \\ \end{array} } \\ \end{array} $$
(9)

where

\( p\left( {X \to X^{{\prime }} } \right) \) :

is the probability of replacing solution \( X \) by solution \( X^{\prime} \),

\( \left| {{\text{A}}_{O} } \right| \) :

is the size of the observed area of interest of solution \( X \),

\( \left| {A_{O}^{'} } \right| \) :

is the size of the observed area of interest of solution \( X^{{\prime }} \),

\( T \) :

is the current temperature

Each loop (points 5 to 15), where the temperature does not change, is terminated when at least one of the following conditions is met:

  • Number of transformations \( k \) exceeds the maximum value \( k_{max} \).

  • Number of replacements \( r \) exceeds the maximum value \( r_{max} \).

  • Number of infeasible solutions generated \( e \) exceeds the maximum value \( e_{max} \).

4 Implementation

The DOAPO model and the proposed algorithm have been implemented into the Tactical Decision Support System (TDSS). This system works with the real geographic data and supports the basic elements and functions following from the model formulation, such as:

  • Definition of the area of interest in the form of a polygon.

  • Estimation of a terrain elevation in an arbitrary point inside the area of operations based on the Digital Elevation Model (DEM).

  • Management of the database of topographic and other objects based on the Topographic Digital Data Model (TDDM). Each object is represented by a polygon with or without holes and its parameters (e.g. object height).

  • Management of enemy units and their basic parameters.

  • Calculation of the visibility from a number of points to a specified polygon, taking into account the occlusion effect caused by non-transparent objects.

Different objects of the TDDM model are used for different purposes:

  • Non-transparent objects, such as buildings, forests and fences, as obstacles which may occlude of some portion of the area of interest.

  • Objects, such as forest and vegetation strips, as possible shelters.

  • Roads and communication infrastructure as possible escape routes.

In the implementation, infinite sets of points (e.g. \( A_{O} \), \( C \), \( R \)) or continuous variables (coordinates) are simplified to finite sets and discrete variables by rasterization. The coverage of the area of interest is computed in each square lying inside the area of interest independently. The size of the coverage \( \left| {A_{O} } \right| \) is represented by a number of squares which have the VLOS from any observation post. The precision of the results can be influenced by setting the size of squares (rasterization step).

The main dialog of the DOPAO model is shown in Fig. 4. The number of observation posts to be deployed are specified in the upper-left corner. Below, the tactical requirements and conditions based on formulae (4) to (8) can be specified; each condition is optional. Basic visibility parameters (height of observer, height of objects, visibility range) can be set on the right, but must be the same for all observation posts. The rasterization step can be also specified. The visualization of results can be seen in Fig. 5. Locations of three optimization posts (A, B, C) were optimized. The area of interest is bounded by a blue line, green color represents the area observed from the posts, red color means unobserved area. The total coverage is 88.36%.

Fig. 4.
figure 4

Implementation of the DOPAO model in the TDSS

Full size image
Fig. 5.
figure 5

Implementation of the DOPAO model in the TDSS (Color figure online)

Full size image

5 Experiments and Results

Five scenarios have been designed as benchmark problems to verify the algorithm proposed for solution. Table 1 shows their basic parameters. The scenarios reflect the typical reconnaissance operations. Individual scenarios can be characterized as follows:

  • dop01: small area of interest, flat terrain, no obstacles.

  • dop02: small area of interest, slightly uneven terrain, no obstacles.

  • dop03: medium-sized area of interest, uneven terrain, high density of obstacles.

  • dop04: large area of interest, uneven terrain, low density of obstacles.

  • dop05: very large area of interest, very uneven terrain, medium density obstacles.

Table 1. Scenarios
Full size table

Table 2 presents conditions for locations of observation posts required in the scenarios as defined in Sect. 2 – see formulae (4) to (8).

Table 2. Conditions for scenarios
Full size table

The optimizations were conducted on a computer with the following parameters: Intel Core i7-7700 CPU @ 3600 GHz, 32 GB RAM. The parameters of the algorithm (see Fig. 3 in Sect. 3) were set as follows: \( T_{max} = 100 \), \( T_{min} = 5 \), \( \alpha = 0.9 \), \( k = 500 \), \( r = 200 \), \( e = 500 \), a single variable randomly selected was changed in a transformation. Rasterization step was set as follows: 2 m for scenarios dop01, dop02 and dop03, 4 m for scenario dop04 and 5 m for scenario dop05.

Table 3 shows the results of optimizations. The table records the total coverage (in percent) as well as the time needed for optimization (min:sec). The objective was to find the best solution for individual scenarios and conditions. In all cases, the coverage of the area is above 89% except for scenario dop03 where it is below 80%. The reason in this case is the high density of obstacles in the area of interest, and requirements that posts has to be near shelter (edge of forest) and outside the area of interest. Even so, the total coverage is more than 78%. The optimization time shows its dependence on the size of the area of interest and the number of observation posts to be deployed.

Table 3. Results
Full size table

The situation of scenario dop03 is illustrated in Fig. 6. On the left, an environment is shown, the coverage (78.65%) is on the right.

Fig. 6.
figure 6

Scenario dop03

Full size image

6 Conclusions

In the paper, the DOPAO model (Deployment of Observation Posts in the Area of Operations) was formulated and the solution based on stochastic approach using simulation annealing principles was proposed. The implementation in the Tactical Decision Support System (TDSS) was introduced. A set of experiments were designed as benchmark problems. All scenarios reflect the parameters of typical reconnaissance operations. Various conditions and tactical requirements were set.

The results show that the algorithm is able to find high quality solutions even for scenarios with (a) hard limiting conditions (shelter, escape route), (b) complex environment (high density of obstacles, uneven terrain), and (c) high number of observation posts (30 in case of scenario dop05 which is 60 independent variables in a solution).

The future work of the authors will be aimed at statistical evaluation of the results on the proposed scenarios, assessment of the performance of the algorithm in regard to the tactical requirements and complexity of the environment, and comparison of results with other probabilistic approaches and methods (in simpler cases even with the optimal solution found using the brute force search).