## Occupation-aware planning method for robotic monitoring missions in dynamic environments

Yaroslav Marchukov and Luis Montano

Instituto de Investigaci´n en Ingenier´a de Arag´n (I3A), University of Zaragoza, Spain o ı o yamar@unizar.es, montano@unizar.es

## Abstract

This paper presents a method for robotic monitoring missions in the presence of moving obstacles. Although the scenario map is known, the robot lacks information about the movement of dynamic obstacles during the monitoring mission. Numerous local planners have been developed in recent years for navigating highly dynamic environments. However, the absence of a global planner for these environments can result in unavoidable collisions or the inability to successfully complete missions in densely populated areas, such as a scenario monitoring in our case. This work addresses the development and evaluation of a global planner, MADA (Monitoring Avoiding Dynamic Areas), aimed at enhancing the deployment of robots in such challenging conditions. The robot plans and executes the mission using the proposed two-step approach. The fi rst step involves selecting the observation goal based on the environment's distribution and estimated monitoring costs. In the second step, the robot identi fi es areas with moving obstacles and obtains paths avoiding densely occupied dynamic regions based on their occupation. Quantitative and qualitative results based on simulations and on real-world experimentation, con fi rm that the proposed method allows the robot to effectively monitor most of the environment while avoiding densely occupied dynamic areas.

Keywords:

Dynamic environment, Occupation-aware global planning, Monitoring mission

## 1. Introduction

The paper focuses in the development of a global planner for dynamic environments. Traditional planning techniques designed for static scenarios are no longer applicable, as the planned trajectories need constant re-planning to navigate through areas temporarily occupied by moving obstacles. The global planner must be developed with context awareness, tailored to the speci fi c mission at hand. Traditional criteria such as the shortest path or minimum time to the goal are no longer universally applicable. In this work we center in environment monitoring missions, which impose some constraints and characteristics to the designed planner. The robot's mission is to observe an entire environment, given the map of the scenario containing the static obstacles (walls, furniture, etc). However, the presence of dynamic obstacles, whose motions are unknown and introduce uncertainty into the scenario, presents an additional challenge, addressed in this work. The robot must avoid colliding with them or traversing these areas, whilst keeping the main mission of monitoring the most part possible of the environment. Figure 1 illustrates two snapshots of a real-world experiment in which the proposed method has been applied. Trajectory planning for static or sporadically changing scenarios, or a purely reactive approach to obstacle avoidance, are inadequate. Even if these methods consider surrounding moving obstacles, they fall short because a new trajectory must be continuously computed to monitor the majority of the scenario at any given moment while simultaneously managing its dynamic nature. The robot tackles the challenge of balancing collision risk with mission completion. Once the scenario is observed, either completely or partially due to occlusions provoked in dynamic dense areas, the mission is considered complete. Thus, the problem solved in this work is the development of a global planner to monitor a scenario, avoiding obstacle-crowded regions.

Apotential application involves monitoring factories, warehouses, or supermarkets, where a robot can be utilized to search for objects or for environment surveillance, maintaining the maximum visibility as possible

(a) Initial plan. (i) The robot computes the goal from where to monitor the next set of points (red points). (ii) There are dynamic obstacles in the scenario observed by the robot. (iii) The robot builds the dynamic areas based on their movement (red polygons) and computes an initial global plan to reach the goal (blue line).

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-8e88798d-fefd-4aa6-a7a0-7a5b8a78bcea.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-b67b0a61-f2bb-44f2-97c3-52d620346e91.jpg)

(b) Plan update based on the movement of obstacles. (i) The robot updates the monitored part of the scenario. (ii) It enlarges the dynamic areas as the obstacles move. (iii) A new plan is obtained surrounding the updated dynamic areas, so as not to disturb humans and avoiding to collide with them.

Figure 1: Monitoring mission in presence of humans.

in every moment. The presence of human workers or other robots acting as dynamic obstacles, introduces uncertainty in the global plan, necessitating its recomputation at each control interval. Additionally, in these scenarios, employees typically move within designated working areas. The robot must avoid these densely populated dynamic areas to reduce the risk of collision and ensure thorough environmental observability. There are three main reasons for the robot to avoid these areas. The fi rst reason is to prevent any disturbance to moving obstacles. The second is to avoid collisions in populated areas, mainly in narrow and highly populated areas, in which the robot could cause signi fi cant damage to people or even break itself. The third is trying to keep the maximum visibility of the scenario, because the moving obstacles could keep unobserved a part of the monitored area. Therefore, it is crucial for the robot to identify these dynamic areas, enforcing to the motion planner to move the robot towards clearer areas that can be correctly monitored without a great reduction of the observed areas, allowing to re-visit them when possible. Aconclusion of this work is that it is needed to integrate specif and context-aware global planners with ef fi cient local planners to improve the success of the mission.

Though the monitoring application has been addressed to frame the desired robot behavior, the techniques developed in this work could be used in other applications in dynamic scenarios, in which the robot has to avoid areas with a high density of moving ob- stacles (e.g. robotic services in airport or train station halls).

The remainder of the paper is organized as follows. Section 2 discusses the related work. In section 3 the general system concept and the contributions are described. Section 4 presents a general overview of the proposed approach to solving the problem of monitoring the scenario. Section 5 de fi nes the variables and tools used along this work. Section 6 explains the offl ine planning aspect of our method. Section 7 provides details on the online method used by the robot to select direction and goals, including path planning to avoid dynamic areas. Results from quantitative and qualitative evaluation based on simulations and on real-world experiments, respectively, are presented and discussed in Section 8. Finally, conclusions are detailed in Section 9.

## 2. Related Work

The monitoring of the environment can be approached in various ways. Works such as [1] and [2] propose coverage solutions that involves repeatedly covering the scenario over a speci fi c period, and [3] makes a review of coverage techniques. Patrolling applications are presented in [4], [5], [6], and [7], where robots follow precomputed paths (patterns) cyclically. Works as [8] and [9] develop environment exploration tasks without a preexisting map. Notably, these approaches are designed for static scenarios, and therefore

are not longer valid for dynamic ones, because of effectiveness, ef fi ciency and safety. The method developed in this work deals with environment monitoring tasks context. It assumes a prior static map is available, and leverages this information to plan future goals while avoiding some dynamic areas that prevent monitoring and/or lead to potential collisions.

Much of the recent work has primarily focused on navigation among dynamic obstacles. Studies such as [10][11][12][13] develop and evaluate various local planners in human-crowded environments. These methods emphasize robot navigation among pedestrians, assessing several classical and social metrics. However, they do not incorporate a global planner that explicitly accounts for social behaviors when computing and adapting the paths, nor do they anticipate the robot's actions to avoid risky and crowded areas.

To anticipate possible collisions, some works focus on developing global planners that integrate social rules into classical path-planning algorithms. In [14], an RRT* global planner is adapted by computing a global plan based on learning the weights of its cost functions from human trajectories, thereby allowing the planner to mimic demonstrated behaviors. Depending on the learned context-speci fi c weights, the computed path may or may not intrude into human personal space. In [15], the authors modify the classic Elastic Band (EB) approach by incorporating human movement patterns to facilitate human-robot co-navigation. The Fast Marching Method (FMM) is used for social navigation in [16], where an 'actuation' space around humans is included to anticipate their movements. The work in [17] employs an optimization approach to generate paths that simulate possible human trajectories. In [18], the authors use A* to reason about the spatial relationship between robots and humans over time, applying a Gaussian-based social cost model to predict human movements. However, a key limitation of all these works is the low number of humans considered in the avoidance process. Additionally, analyzing each person individually can signi fi cantly increase computation time, making real-time calculations prohibitively slow.

Some works combine global and local planners. In [19], the A* algorithm uses a heuristic cost derived from the Dynamic Object Velocity-Time Space (DOVTS) to expand nodes that do not lead to potential collisions. Similarly, in [20], the authors develop a navigation system based on an FMM path planner that integrates social costs to avoid small groups of people. However, like the previously mentioned approaches, these methods focus on scenarios where the robot is forced to navigate among humans. In contrast, there are situations where it may be more ef fi cient for the robot to bypass densely occupied areas, if possible.

The objective of our work is to enable the robot to plan and navigate in larger environments containing static obstacles as well as small or large groups of people moving through the space. Depending on the application context, and the potential risks of collision or reduced visibility in crowded, dynamic areas-such as in monitoring tasks-the global plan and motion execution will adapt during each control period. In designing the global plan, we incorporate social principles, as outlined in [10], such as safety, politeness, understanding other agents to reduce potential con fl icts before collisions, and contextual appropriateness. Additionally, we consider the concept of people density in different parts of the environment to identify dynamic areas, guiding the decision of whether to enter a populated area or avoid it.

The authors of [21] propose a method to avoid regions populated by obstacles. They develop a Crowdbased Dynamic Blockages (CBDB) layer to identify and evaluate whether to traverse regions with obstacles, based on their density. Our method is similar in concept but with some key differences. Our approach, MADA , is less conservative regarding obstacle-populated regions. Instead of considering large regions as in CBDB, the robot de fi nes dynamic areas to be avoided based on the observed movement of obstacles. The path planning approach in [21] requires evaluating several paths to select the best one, whereas MADA builds the dynamic areas and computes a single path. Given these similarities, we will compare the performance of CBDB, employed in a monitoring mission, against our developed MADA approach.

Additionally, we demonstrate the advantages of integrating dynamic areas with a social path planner in a monitoring mission. We incorporate the FMM-based social path planner from [16] into our proposed method. By including information about dynamic areas, we show that the robot improves mission outcomes in terms of collision reduction and monitoring ef fi ciency, even when using social planners like [16] for monitoring missions.

## 3. System concept and contributions

The system concept is illustrated in the sequence of Fig.2, where the robot monitors the environment, selects the next goal (next region of interest for monitoring), computes a fi rst trajectory towards it, identi fi es the risky dynamic areas, re-computes a path avoiding them to the next region of interest, iteratively repeating the process

Figure 2: Illustration of the monitoring mission. In Fig.2(a), the robot (depicted in blue) monitors the scenario in the presence of dynamic obstacles (depicted in red). Fig.2(b) illustrates the robot's planned path towards a region to be monitored. The zones observed and not observed by the robot during the motion up to the current location are represented in white and green, respectively. The robot (depicted as a blue square) follows the path (shown as a blue line) to reach the next goal for making new observations. In Fig. 2(c) while following the path, the robot monitors the scenario, observes dynamic obstacles (depicted as black rectangles), and builds dynamic areas (depicted as red polygons). These dynamic areas are constructed based on the observed positions (depicted as red points). If the dynamic are dense enough, the robot obtains a new goal and calculates a new path to reach the goal throughout the observed and the unknown areas, avoiding the risky dynamic areas, as shown in Fig.2(d). Due to the movement of obstacles, the dynamic areas are extended. Consequently, the robot adjusts its path to traverse less occupied dynamic areas, as depicted in Fig.2(e).

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-b29684e5-0a4f-4cb2-bc01-8461cd0776d7.jpg)

until the mission is completed. It's crucial to highlight that only dense dynamic areas, categorized as risky, infl uence their traversability. Conversely, non-dense dynamic areas do not prevent them from being crossed, allowing the robot to navigate through them while avoiding obstacles that may emerge in these regions. Note that in a monitoring mission, the robot has not to cover all the scenario surface as in a coverage mission. Therefore, the robot only moves into a region up until it is completely observed from a viewpoint, which depends on the visibility range of the sensor used for monitoring, as can be seen in Fig.2. Once that region is observed, the planner computes a new path to the next selected region.

Thus, the contribution of this work this work is the development of a global planner to monitor a scenario, avoiding obstacle-crowded regions. The method follows a two-step approach to plan and execute monitoring missions in dynamic environments, ensuring safety in the context of such missions. In the fi rst step, the Of ine planner fl computes an adjacency graph from the prior static map, guiding the process of planning the mission, by connecting the successive areas established as subgoals to be reached. In the second step, an Online planner , based on the previous graph, detects every control period the dynamic areas and re-plans the path either to avoid the potentially risky ones, or to traverse them, depending on an occupancy criterion.

The method is evaluated in different scenarios, comparing the results based on metrics with other two techniques, one more conservative regarding the risky areas, and the other greedy, in which there is not an explicit representation of dynamic areas for planning paths taking them into account. An experimental evaluation was performed on a real robot to demonstrate the method's

Figure 3: System Overview. The output variables in each module are explained in section 5.1

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-74cbf4a3-ed03-482f-891e-96b0f0795f47.jpg)

performance in real-world conditions.

## 4. System overview

The method computes the global plan and executes the motion in two-steps, as illustrates Fig.3:

- · Of ine planning: fl From the prior static map, the fi rst step obtains the distribution/layout of the environment, by splitting the scenario into partitions and obtaining the adjacency graph between them, to guide the process of planning the mission. During this phase, the workload cost for monitoring each partition and the time needed to move between partitions are estimated. These estimates are vital for developing an ef fi cient plan to observe the entire scenario during the monitoring mission.
- · Online planning: Once the mission starts, this planner selects the next region to monitor, based on the estimates of the of fl ine planner, and computes the goal position where the robot will see this region. Then, the planner computes the trajectory towards the new goal. This trajectory avoids risky dynamic areas based on the occupation level of the dynamic obstacles. Once the execution of the initial plan is launched, the online planner recomputes the initial trajectory towards a new goal when a new risky dynamic area is detected, based on the area occupancy, avoiding this area, executing the plan with a path follower.

During the process, the method tries to dynamically compute trajectories that maximize the observed scenario, whilst avoids returning to areas already seen, if it can be achieved. This way, the fi nal trajectory will be as shorter as possible. Figure 4 represents the whole trajectory followed by the robot to complete the mission.

Sections 6 and 7 describe in detail the Of ine planfl ning and the Online planning , respectively. To understand the whole process, the Figures 5, 6, and 7 depict the successive steps followed. In Fig.5, after splitting the scenario into partitions, a graph of the partitions is obtained. This graph will serve as a guide for monitoring the whole scenario. In Fig.6 the steps of the Online high-level planning are depicted, for reaching a fi rst region of interest as a goal (in red) in Fig.6(c) from the robot position in Fig.5(a). The steps of the Online lowlevel planning are shown in Fig.7, in charge of detecting the dynamic areas to be avoided, and planning the trajectory towards a new goal in a next region of interest. This way the robot simultaneously monitors the new region and is able to inspect the previous avoided one from a new point of view.

## 5. Notation and basic tools

## 5.1. Notation

We consider a differential robot equipped with a 360º fi eld of view laser. The robot monitors a 2D world rep-

Figure 4: The robot travels along trajectories away from static obstacles during the mission, monitoring in this case the most part of the scenario.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-dcd72af5-08b0-4aba-a3e8-1429d369e01c.jpg)

resented as a grid, de fi ned by the variable M , which corresponds to the static map of the scenario. The variable x represents a position on the grid and x denotes a set of positions on the grid. M x ( ) = 0 when x contains an obstacle and M x ( ) = 1 when it is free space. The positions of the static obstacles are expressed as x so . Employing the static map M with x so , the robot splits the scenario into partitions expressed as P , see Fig.5(b). The adjacency between the partitions are obtained with the graph GP , see Fig.5(c). In order to choose the next goal to go to make observation, the robot evaluates all the possible directions computing the tree TG , Fig.6(a). Then, the branch of the minimum cost b ∗ ∈ TG is selected. Then, the robot chooses the next partition from the branch, denoted as p ∗ ∈ b ∗ . The observation of the partition is made from the computed goal, expressed as xg , see Fig.6(c).

The position of the robot is xr and its visibility range is rv . All the visible positions from xr are denoted as x v . The robot moves in a scenario with dynamic obstacles, whose positions are denoted as x do . When the robot observes the motion of dynamic obstacles, see Fig.7(a), it stores their trajectories χ do and constructs the dynamic areas, expressed as A obs d = [A obs d 1 , ..., A obs dN ], x do ∈ A obs d , see Fig.7(b). In order to move to xg , the robot computes the path π , de fi ned as a sequence of adjacent positions, depicted in Fig.7(c). The path π will avoid the dynamic areas A obs d , based on the density of the obstacles within them. So that, if the areas are dense, they are considered risky and will not be traversable. To determine if an area is dense, an occupation threshold Oth is applied. To follow the path π , the robot obtains the next destination xdest ∈ π , computing the linear and angular velocities to apply, ( vr , ω r ).

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-102889e8-e496-4319-abc8-188aff82011a.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-f8666207-3309-4fdf-818d-e3d52c07f119.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-2995e5d4-64fc-4f4f-b899-bb48c95f37b5.jpg)

(a)

Scenario

(b) Scenario partition P

(c) Graph computation GP

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-fb4d820f-41e2-4464-b99c-12ec5f680b38.jpg)

Figure 5: Of fl ine planning to extract information of the scenario shown in Fig.5(a). Fig.5(b) shows the partition of the scenario, that will be sequentially visited and used to estimate the cost to monitor each of them. Fig.5(c) illustrates the graph of the partitions, which is used to know the connections between partitions and to estimate the cost of traveling between them.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-409e47d7-947c-4b87-a125-e851efc79c68.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-a7163a76-c1cf-4e4b-8a5a-b00810b3a26e.jpg)

(a) Tree computation TG

(b)

Branch selection

b

∗

(c) Partition selection p ∗ (red) and goal computation xg (blue)

Figure 6: Online high-level planning of the proposed approach to select the next goal to make observations. At each moment, when the robot searches a new goal to observe the next set of points, it executes these sequence of methods. Fig.6(a) illustrates the tree obtained for the position of the robot of Fig.5(a). In Fig.6(b), the robot selects the branch of minimum cost from all the possibles of the tree. Fig.6(c) shows the selected partition to be observed (red points) from the computed goal xg (blue star).

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-9dd7ad09-f384-4904-8b5b-7c6cb7505b0b.jpg)

- (a) Robot observing dynamic obstacles

(b) Dynamic areas computation A obs d

(c) Path planning π and path following

Figure 7: Online low-level planning to avoid dynamic obstacles. Fig.7(a) depicts the robot (blue square) going to the goal (blue star) to observe the points of the partition (red points), in presence of moving obstacles (grey rectangles). In Fig.7(b), the robot builds the dynamic areas (red polygons) from the movement of the obstacles (red points) in successive instants. Fig.7(c) illustrates the obtained path (blue line) to avoid the dynamic area. The red line from the robot center represents the destination to the point on the path to follow it, computing the velocity commands to drive to this destination.

The Fast Marching Method (FMM) [22] plays a crucial role in various aspects of our proposed monitoring mission approach, offering ef fi ciency and versatility. We leverage this mathematical tool across different stages, bene fi ting from its unique properties to compute diverse intermediate results. FMM stands out among other path planners for our purposes, such as Probabilistic Roadmaps (PRM) [23] and various versions of Rapidly-exploring Random Trees (RRT) [24, 25, 26, 27], by providing a balance between speed and optimality. Unlike A* path planning method [28], FMM excels by requiring only one gradient computation from the agent's position to all possible goals. This ef fi ciency signi fi cantly reduces the computation time, making it a favorable choice for our approach. Moreover, FMM enables the computation of paths that ensure a safe distance from obstacles, contributing to the maximization of the fi eld of view for monitoring, enhancing navigation safety to mitigate collision risks, avoiding to be blocked by moving obstacles near the walls, or increasing the visibility of obstacles in corners, following some social rules described in [10].

FMM works on a grid map, and involves propagating a wavefront from a source location over a surface. The distance from the source is computed at all points (cells) during propagation, using the accumulated distance from the neighbors, ensuring that surrounding obstacles are always accounted for:

$$| \nabla D | F = 1 \quad \quad \ ( 1 )$$

where ∇ D represents the distance gradient from the source position and F is the velocity of the wavefront.

F = 0 when the cell contains an obstacle, and F = 1 if the cell is free space. With these velocity values, F = [0 , 1], using the FMM for classical path planning causes the wavefront to propagate uniformly in all directions, avoiding obstacles and obtaining the distance gradient. By simply descending this gradient from any point, it will lead to the source of the wavefront, thus obtaining the shortest path to the source point while avoiding obstacles. FMM is used to split the scenario into partitions in the Of fl ine planning, and to compute the trajectories which avoid the dynamic areas during the Online planning.

In the following sections, we will explain how we adapted FMM to take advantage of its properties for the proposed method.

Algorithm 1 Scenario partition

Require: Static map M , static obstacles x so

- 1: ∇ Dso ← compute gradient ( x so , M )
- 2: x p ←∅ ∇ , Dso ′ = ∇ Dso
- 4: [ vp , xp ] ← f ind max ( ∇ Dso ′ )
- 3: while any ( ∇ Dso ′ ) &gt; 0 do
- 5: x p ← xp
- 6: ∇ Dso ′ ( xp -vp , xp + vp ) = 0
- 7: end while
- 8: ∇ Dc ← compute gradient ( x p , ∇ Dso )
- 9: P ← obtain partitions ( ∇ Dc )
- 10: return P

## 6. Of fl ine planning

Before the mission begins, the robot extracts of fl ine the information of the environment in which is moving. In this section we describe the of fl ine planning procedure. The division of the scenario in partitions is explained in Section 6.1. Section 6.2 details the computation of the adjacency graph from the obtained partitions.

## 6.1. Scenario partition

Several studies have addressed scenario partitioning, such as [29] for room identi fi cation and [30] for robotic room-by-room clearance. However, for our monitoringfocused problem, partition shapes are not critical. The robot only needs information on partition size for observation times and connections between partitions to select the next one, discarding those potentially unreachable due to dynamic obstacles. Our approach employs the Fast Marching Method (FMM) for scenario partitioning, incorporating static obstacles and using interpolated distances to propagate the wavefront between the points of the partitions, differentiating from traditional Euclidean distances employed in Voronoi tessellation [31].

Algorithm 1 describes the method for splitting the environment with FMM, as illustrated in Fig.8. The gradient from the static obstacles, ∇ Dso , is computed from the map of the scenario M . The wavefronts are initialized from the static obstacles x so . The maximum value of the gradient, vp , is searched iteratively and is placed at the partition point xp . This position will be the furthest point from the obstacles within the partition and will be a source of the wavefront of FMM. The values of the gradient within the distance vp are set to zero (equivalent to an obstacle), to avoid selecting several wavefront sources in the same space, Fig.8(a). Then, the gradient ∇ Dp , Fig.8(b), is obtained by propagating the wavefront from all the partition points xp ∈ x p using

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-47e76ac1-d353-4905-918c-bf70e2ac23e1.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-2feac824-7556-4493-a9a3-23839985756e.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-e7a1c80c-d858-4e93-ab14-0b9b74fac3e4.jpg)

(a)

Maxima of

∇

Dso

(b)

Gradient

∇

Dp from

x

p

(c)

Partitions

P

Figure 8: Environment partition procedure. In Fig.8(a), the maxima of ∇ Dso are found. These maxima correspond to the point of maximum value of the gradient in each partition of the environment x p . Fig.8(b) illustrates the gradient ∇ Dp , obtained by propagating the wavefronts from x p . The partitions of the scenario are extracted from ∇ Dp and depicted in Fig.8(c).

the distance transform ∇ Dso as the velocity of propagation. This ensures that the wavefront propagates faster in wide spaces, such as rooms or corridors, slowing down and colliding in narrow spaces, such as doors, Fig.8(b). Finally, the partitions are obtained as the regions covered by each of the wavefronts, coming from x p , as illustrated in Fig.8(c). As illustrated in the fi gure, the resulting partitions have a polygonal shape and a notable feature is that all straight lines connecting each point on the polygon edge with xp lie within the polygon. Therefore, if the visibility range of the sensor rv is large enough, the robot moves towards xp to observe the entire partition, not needing to move to other positions inside the region for this observation, thus aiming to reduce the total mission time.

## 6.2. Graph computation

The graph of the environment GP is obtained from the adjacency between the different partitions described in the previous subsection. Figure 9 illustrates the adjacency graph of the partitions obtained in Fig.8(c). This ensures that the robot always has the information about the distribution of the different partitions in the environment, in order to properly choose the next one to monitor. This graph serves to estimate the cost of observing the partitions and travelling between them, to guide the monitoring of the whole scenario.

As can be seen in Fig.9, multiple nodes or edges are located in the same regions, such as corridors or rooms. This occurs because the nodes' positions are adjusted based on the available free space, i.e., the distance to nearby obstacles. This approach has two main advantages. First, it ensures that the robot can monitor the entire partition (assuming suf fi cient view range), which wouldn't be guaranteed by simply traversing the edge if nodes were only at the beginning and at the end of

Figure 9: Graph GP for partitions of Fig.8(c).

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-09a695bc-5764-4128-b79f-b2ed83337584.jpg)

the corridor. Second, in dynamic environments, certain regions may become non-traversable or need to be avoided. Hence, it is more ef fi cient to consider smaller, adjusted partitions rather than large areas. For example, in an elongated corridor, it is better to avoid only the sections occupied by dynamic obstacles, rather than discarding the entire corridor.

## 7. Online planning

As represented in the diagram of Fig.3, once the mission starts, the robot selects new goals and moves to them avoiding the dynamic obstacles. High-level planning selects the partition p ∗ from GP obtained in the Of fl ine planning, computing the new goal xg to visualize the partition. The low-level planning detects the dynamic areas A obs d . If they exist, a new path avoiding them is computed and executed, with the robot following it by applying the computed velocity ( vr , ω r ). Both planners are explained in the next Sections 7.1 and 7.2.

(a) Example of tree TG

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-0eae1a3d-5423-49c7-a90c-4535aa2337c9.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-748c35fb-760d-4091-81a7-e8af7de362e1.jpg)

(b) Unreachable partitions due to obstacles

Figure 10: Computation of the tree graph TG .

## 7.1. High-level planning

The next goal to be reached in the next region of interest is calculated by applying in sequence four procedures: tree computation, branch selection, partition selection and goal computation. They are explained in the following subsections.

## 7.1.1. Tree computation

Firstly, the robot has to know the direction where to move to continue monitoring the scenario. Since, the robot has the information of the scenario to monitor, that is the partitions P and the graph GP , it must select a sequence of edges of the graph (branch) in order to know the direction. For this purpose, we compute the tree from the graph, denoted as TG , Fig.10. Its root or origin is the partition where the robot currently is and the edges are selected executing Dijkstra's algorithm [32], obtaining the connections between the partitions. To execute Dijkstra, we consider the cost to travel between partitions, computed as ct = dij / vmax , where is dij is the Euclidean distance between the vertices of partitions i and j and vmax is the maximum robot linear velocity. This way, we obtain the tree with all the possible paths to reach all the partitions, traveling between the partitions, as illustrated in Fig.10(a). This ensures that the path formed by each branch of the tree represents the path of minimal cost from the robot's partition to every partition in the scenario.

The knowledge of the possible branches is also important for our problem since there are dynamic obstacles moving in the scenario. Some of the tree branches might be unreachable. For instance, in Fig.10(b) some partitions are discarded to be reached because the paths to them in the tree are blocked by the moving obstacle at the left area in the fi gure. This information is included in the Low level planner, as will be described in Section 7.2.2.

## 7.1.2. Branch selection

Due to the dynamism in the environment, it is not possible to know the best direction to take, as it may not be reachable. Therefore, we propose to use the Greedy approach to select the branch, minimizing the estimated cost of traversing ct ( bi ) and monitoring cm ( bi ) the partitions of branch bi ,

$$b ^ { * } = \underset { b _ { i } \in \mathcal { T } _ { \theta } } { \arg \min } ( c _ { t } ( b _ { i } ) + c _ { m } ( b _ { i } ) ) \text{ \quad \ \ } ( 2 )$$

where,

$$c _ { t } ( b _ { i } ) = d i s t ( \pi _ { b _ { i } } ) / v _ { m a x } \text{ \quad \ \ } ( 3 )$$

with π bi denoting the path formed by the sequence of partition points xp of the partitions of branch bi (that is, the sequence of edges), and dist () expresses the function to sum the Euclidean distances between xp of π bi .

The estimated monitoring cost cm ( bj ) in the partition P j , is calculated with the following expression, which depends on the visibility range rv :

$$\text{to} \quad & c _ { m } ( b _ { j } ) = \begin{cases} \begin{array} { c } 1, & r _ { v } \geq d _ { m a x _ { j } } \\ r _ { v } \frac { | \mathbf x _ { m s _ { j } } | } { | \mathbf x _ { l _ { j } } | } \left ( \frac { d _ { m i n _ { j } } } { r _ { v } } \cdot \frac { d _ { m a x _ { j } } } { r _ { v } } - 1 \right ), & r _ { v } < d _ { m a x _ { j } } \end{array} \end{cases} ( 4 ) \\ \text{for}, \quad & \text{where} \, \mathbf x _ { n s _ { j } } \text{ denotes the points not yet seen in part} \text{-} \end{cases}$$

## 7.1.3. Partition selection

where x nsj denotes the points not yet seen in partition P j , x t j are all the points of P j , dminj and dmaxj are Euclidean distances from partition points xp ∈ P j to the closest and the farthest point of the partition, respectively. If the visibility range of the sensor rv is less than dmaxj , the robot will have to traverse the partition to observe all points. Finally, the total cost of monitoring the branch is computed from the summation of the costs of the partitions included in the branch, cm ( bi ) = P bj ∈ P j cm ( bj ).

Once the branch b ∗ is selected, it is necessary to know the space to be monitored. It is chosen as the fi rst partition p ∗ of the branch with points that have not yet been seen, as illustrated in Fig.11.

## 7.1.4. Goal computation

After selecting the next partition to monitor, the robot selects the goal position to move to, see Fig.12. This procedure is detailed with Alg.2. When the sensor range is larger than the distance from the xp to the farthest point of the partition, the robot is able to visualize absolutely the entire partition, due to the way of constructing the partitions, explained in Section 6.1. The partition point xp is selected as the goal. Otherwise, all the unseen points of the partition are grouped by adjacency,

Figure 11: Selection of the partition of a branch represented in blue. The robot chooses the partition that still has points to be observed, shown in red. The gray colour in the partitions indicates observed points, while the green colour indicates unobserved points.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-5fac2a3e-6151-4275-baa4-e96ad459a8f1.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-92294f7b-a879-4ab8-a5e5-23e5e6ee211e.jpg)

(a) vr ≥ dmaxi so the goal is the point xp of the partition i

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-aad946bc-2c6e-4821-8acb-8c76307e791b.jpg)

(b) The goal is selected as the closest point of non-seen points, in green

Figure 12: Goal selection. In Fig.12(a), the visibility range is greater than the maximum distance of the partition, so all the points are observed from xp . In Fig.12(b), the goal is the closest point from the smallest set of points in the partition to be monitored.

## Algorithm 2 Goal computation

1:

if rv

≥

dmaxi then

2:

3:

4:

5:

6:

7:

xg

=

else

[

x

1

x

∗

xpi

, ...,

=

xg

x

{

x

=

end if

8:

return xg

selecting the one containing the least number of points. The value ∇ Dr ( x ) is the gradient from the position of the robot. The minimum value of ∇ Dr ( x ) allows to select the next goal inside the partition, xg . Whilst the robot moves, the set of unseen points is updated and the routine is re-launched, again selecting the goal as well as the path to it.

{

k

j

x

|

]

←

∣

∣

∣

|

x

j

|

min

(

group points

(

=

min

([

|

x

1

|

, ...,

∇

Dr

(

x

))

,

x

x

nsi

|

x

∈

x

)

k

|

∗

}

])

}

When the robot goes to xp , it is expected to view the partition points directly from there. As soon as the robot reaches the target and does not see those points due to moving obstacles, it remains in standby. Since the movement pattern of dynamic obstacles is unknown, it is not possible to know when they will move. Therefore, once it reaches the goal, a waiting time t wait is set before discarding the occluded points and going to a new goal. This time is estimated as:

$$t _ { w a i t } = 2 \, d _ { m a x _ { i } } / v _ { m a x } \, \quad \quad \quad ( 5 )$$

where 2 dmaxi represents the greatest distance the robot must travel to traverse the partition P i .

## 7.2. Low level planning

During the mission, the robot must effectively track and avoid moving obstacles like humans or robots. Existing human-tracking methods [33, 34, 35] are computationally demanding, posing a challenge for our goal of swift path planning and collision avoidance. We propose identifying positions of dynamic obstacles, regardless of their nature, to construct pre-de fi ned dynamic areas for ef fi cient, proactive avoidance. Local planners for dynamic scenarios like VO [36], ICS [37], and DOVTS [38] could be used for this objective, but in the context of a monitoring application, they do not solve the problem of keeping the maximum visibility whilst possible, increasing the risk of collision in populated areas. Furthermore, a global planner is always needed for accomplishing the missions. Therefore, we propose a new low level planner to manage dynamic scenarios, because the classical global planners for static environments are no longer valid. Our proposed approach allows the robot to follow a path with a wide fi eld of view and avoiding dynamic areas to reduce collision risks.

This section explains how this plan is executed in the presence of dynamic obstacles. In Sect. 7.2.1, we explain how dynamic areas are constructed from the movement of obstacles. Path planning with FMM is detailed in Sect. 7.2.2. And fi nally, the reactive path following method is explained in Sect. 7.2.3.

## 7.2.1. Dynamic areas construction

The procedure of dynamic areas construction is described in Alg.3. The robot detects and updates every control period the moving obstacles x do , computing the dynamic areas A obs d from their trajectories χ do , as illustrated in Fig.13. As it will be explained in section 7.2.2, not all the dynamic areas must be avoided, only those having a high density of obstacles that prevent the mobility inside that region, based on a established occupation threshold Oth .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-174f9e12-a0f8-4f35-a32a-6255e8ff2a78.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-5c1f9ea8-f365-4d2b-bc4a-349aa0fa6634.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-72415cd3-9dfd-43ef-bf66-cbbface20572.jpg)

(a)

Iterative creation of areas

(b) The areas increase with the movement of obstacles

(c) Areas merging after some iterations

Figure 13: Construction of the dynamic areas A obs d from the trajectories χ do traveled by the dynamic obstacles seen by the robot.

## Algorithm 3 Dynamic areas update

1:

x

vo

=

{

x x

|

∈

x

v

,

M x

(

)

=

0

,

x

&lt;

x

so

}

/triangleright Visible obstacles

obstacles, allows to increase visibility in those scenarios, anticipating avoiding or maneuvers inside of the group.

- 2: x do ← update positions ( x vo ) /triangleright Update obstacles list
- 3: χ do ← x do

/triangleright

Insert in trajectories of obstacles

- 4: A obs d ←∅

/triangleright

Initialize dynamic areas

- 5: for each χ doi ∈ χ do do
- 6: A obs di ← convex hull ( χ oi )
- 7: end for
- 8: return A obs d

## 7.2.2. Path planning

In a monitoring mission, the robot would have to move through areas where its visibility fi eld is expanded. It can be achieved if the planned paths traverse areas away from obstacles. In [39], the authors propose using FMM to keep UAVs far from obstacles; a similar approach is adopted here. To do this, the wavefront is initialized setting the static obstacles as source points, and propagated from the static obstacles through the free space, computing the distance gradient from the static obstacles ∇ Dso . Setting the velocity map F = ∇ Dso , propagating the wavefront from a goal position will produce a gradient with higher values in points that are close to obstacles and lower values in points that are far from obstacles. Descending this gradient, the resulting path will traverse points that are far away from the obstacles. Thus, by following these paths, the robot has a lower probability of getting stuck by dynamic obstacles and nearby static ones, leaving clearer spaces for moving.

Another reason for applying such kind of global planning is complying with the named social navigation scenarios as intersection and blind corner , (as de fi ned in [10]). Planning paths as far as possible from the static

At the same time, the information of dynamic areas must be included in the velocity map F , in order to avoid traversing dense areas. The velocity map, used to propagate the wavefront computing the gradient, is de fi ned using the following expression:

$$\underset { \begin{array} { c } \text{$\mathrm{e to $s$} } { - } } & & \\ \text{$\mathrm{e to $s$} } { - } & & F ( x ) \begin{cases} 0, & x \in \{ \mathbf x _ { s o }, \mathbf x _ { d o } \} \\ 0, & x \in A _ { d _ { i } } ^ { o b s }, n _ { d o _ { i } } / | A _ { d _ { i } } ^ { o b s } | > O _ { t h } \\ n _ { d o } ^ { \max } - n _ { d o _ { i } }, & x \in A _ { d _ { i } } ^ { o b s }, n _ { d o _ { i } } / | A _ { d _ { i } } ^ { o b s } | \leq O _ { t h } \\ \nabla D _ { s o } ( x ) + n _ { d o } ^ { \max } + 1, & x \notin A _ { d _ { i } } ^ { o b s }, x \notin \mathbf x _ { s o } \\ \text{tra-} \\ \text{tra-} \end{cases} } & & \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{andout} \, \text{and\,} \, \text{as} \, \text{$\mathrm{n}$} } { - } \, \underset { \begin{array} { c } \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{n}$} } { - } } & \, \text{$\mathrm{n}$} } { \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{n}$} } { \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{n}$} } { \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{n}$} } { \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{n}$} } { \text{$\mathbf $} } { \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-cancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} } { \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{\nabc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} } { \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and} \, \text{as} \, \text{as} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{as} \, \text{as} \, \text{$\mathrm{nominus} \, \text{abc-co-a-dancell} \, \text{and\,} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \text{as} \, \\ \text{tra-} & & \text{$\mathrm{nominus} \, \text{static-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-tilde{\n-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-slope-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-lg-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sm-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-g-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-sigma-$\mathrm{$\mathrm{$\mathrm{$\mathrm{$\mathrm{$\mathrm{$\mathrm{$\mathrm{$\mathrm{$\mathrm{$\mathrm$} } } { - } } & & \text{$\mathrm{$\mathrm{$\mathrm{$\mathrm{$\mathrm$} } { - } & \text{$\mathrm{$\mathrm{$\mathrm{$\mathrm$} } { - } & \text{$\mathrm{$\mathrm{$\mathrm$} } { - } & \text{$\mathrm{$\mathrm{$\mathrm$} } { - } & \text{$\mathrm{$\mathrm$} } { - } & \text{$\mathrm{$\mathrm$} } { - } & \text{$\mathrm$}$$

Dynamic obstacle density, denoted as ndoi / | A obs di | , is computed by considering the ratio of the number of points occupied by obstacles within a dynamic area i ( ndoi ) to the total number of points in this area ( | A obs di | ). In this context, the function F x ( ) is assigned a value of 0 in positions where static or dynamic obstacles are present, as well as in those within dense dynamic areas de fi ned by the Oth threshold. It takes non-zero values in positions corresponding to non-dense areas or free space, with a priority for the latter. As follows from eq.6, static and dynamic obstacles are treated similarly in terms of avoidance. However, dynamic obstacles also contribute to de fi ning dynamic areas, helping to avoid crowded regions.

From F values, the robot computes the gradient, as seen in Fig.14. The dynamic areas of Fig.14(a) produce higher values of gradient ∇ D in Fig.14(b). Thus, descending the gradient, these areas have a lower priority compared to free space, obtaining a path π surrounding them.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-1a61a899-5190-4108-a67d-5f53bf40d083.jpg)

(a) Velocity map F in presence of dynamic areas

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-c02ef635-07be-4656-bb3c-54af0b2cefbc.jpg)

(b) Gradient obtained using F

Figure 14: Inclusion of the dynamic areas of Fig.13(c) in the path planning. The velocities propagation is depicted in Fig.14(a). by the robot for navigation is illustrated moving obstacles are removed from the inaccessible. Cells corresponding to dense dynami values and will be surrounded to avoid The robot (red square), when navig star), prevents fi nding paths (red dashed lines) through dense dynamic areas. Instead, it will circumvent these dynamic areas (white line), covering a larger distance but evading risky spaces.

## 7.2.3. Path following

A simple path follower has been developed, which acts as a reactive navigation method, simultaneously following the path, computing velocities compliant with the kinodynamic constraints, and avoiding the surrounding static and moving obstacles. It is not the a central piece in this work and it could be substituted by other reactive planners. It proceeds in two steps: selecting the destination point xdest with Alg.4 and adjusting the velocities to reach this destination by means of Alg.5.

The next subgoal destination is selected in Alg. 4 on the global path π , considering a larger or shorter distance from the current robot position as a function of its distance to the closest obstacle. Figure 15 outlines the idea and represents the variables involved in the procedure. The value of d π -so is derived directly from the gradient of Dso at the positions of the path. The algorithm iterates while the distance between the robot and a path point, denoted by dr -π ( x ), is not greater than the distance from this point to the closest obstacle. In the case that dynamic obstacles are detected, a safety distance of 2 Rr is incorporated to enhance the safety of the robot. This safety distance affords the robot additional time to maneuver and avoid collisions, in those situations where a dynamic obstacle is approaching.

In the second step, Alg.5 obtains the linear and angular velocities ( vr , ω r ) compatible with the kinodynamic constraints to align to xdest , reducing the linear velocity near the obstacles, being ( vmax , ω max ) the maximum velocities of the robot.

## Algorithm 4 Destination selection

- 1: d max π -o = max d ( π -so , d π -do )
- 2: while dr -π ( x ) ≤ d π -so ( x ) and dr -π ( x ) ≤ d π -do ( x ) -2 Rr do

3:

/triangleright x : current position x ∈ π ; dr -π ( x ) = || xr -x ||

- 4: xdest = x

5:

ddest

-

o

=

- 6: end while

7:

return xdest

,

ddest

-

o

## Algorithm procedure

1:

∆

θ

=

at

2:

ω

=

ω

ma

3:

ω

=

(

∗

&lt;

0

≥

0

$$\underset { \i d, } { \i d } \quad & \frac { 1 } { 4 \colon } \text{ if } \Delta \theta \neq 0 \text{ then } \\ \underset { \i d, } { 5 \colon } \quad & v = \begin{cases} v _ { m a x } * d _ { d e s t - o } * \left ( 1 - \frac { | \omega ^ { * } | } { \omega _ { m a x } } \right ), & | \Delta \theta | < \pi / 2 \\ 0, & | \Delta \theta | \geq \pi / 2 \end{cases}$$

6:

v

=

min v

(

,

vr

+

∆

v

)

7:

8:

9:

else

v

∗

r

∗

r

=

end if

10:

return

(

v

∗

,

ω

∗

)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-f0934e6d-15b2-4639-a2a9-ba1f3f4b5731.jpg)

(a) Farthest destination xdest

(b) Closer destination xdest

Figure 15: Two potential destination selections are presented to follow a path π , situated in proximity to a static obstacle, depicted with black. In Fig.15(a), the robot xr selects a destination xdest at the greatest distance dr -dest and the highest velocity v ∗ , based on the distance to the obstacle ddest -o , with a greater deviation from the path. Fig.15(b) illustrates the robot selecting a destination at a closer proximity with a lower velocity, in order to align more closely with the path.

## 8. Results

This section presents the results of the proposed approach evaluation. The details of the simulations are de fi ned in Section 8.1. The results of the simulations and their discussion are presented in 8.2. Some extensions of the basic method are described in Section min d

(

(

max vmax

,

π

-

so vr

(

+

x

)

,

∆

d

v

)

π

-

do

(

x

))

/

d max

π

-

o

8.3. Comparisons with other methods are presented in Section 8.4. The validation of the proposed approach with experiments in a real robot is carried out in Section 8.5. The videos of the simulations and real-world experiments are available in the link 1 .

## 8.1. Simulation details

In order to provide an exhaustive evaluation of the proposed method, and to highlight one of its utilities, namely its modularity, we consider different aspects:

- · Methods of monitoring the scenario : strategies, occupancy threshold, safety distance from the obstacles, handling of dynamic areas.
- · Environment-dependent aspects : scenario, number of dynamic obstacles, velocity of the dynamic obstacles.
- · Extensions of the approach : projecting obstacle movements, use of other planners.

## 8.1.1. Scenarios

The proposed approach was tested in two distinct indoor scenarios, depicted in Fig.16. These scenarios differ in their structural characteristics, enforcing different kind of obstacle movements. The fi rst scenario, depicted in Fig.16(a), is smaller in scale, featuring shorter corridors and some wide rooms, with Ndo = 10 and Ndo = 25 moving obstacles, representing non-dense and dense environments, respectively, in which concentrate the obstacles. The second scenario, depicted in Fig.16(b), is larger in scale, encompassing a narrow corridor and clearly de fi ned wider spaces, with Ndo = 20 and Ndo = 40 representing non-dense and dense environments.

The visibility range was set to 30 m in the fi rst scenario and 10 m in the second scenario, with a 360° fi eld of view.

## 8.1.2. Moving obstacles

In the kind of scenarios considered in simulations and experiments, the moving obstacles are humans, although they could be other vehicles. We have de fi ned four movement patterns and their time intervals to have a similarity with real behaviours: standing still (5-15 sec.), moving in a straight line (5-20sec.), turning right, and turning left (1-3sec. for both). The randomly generated maneuver is checked for potential collisions in the subsequent time step. It should be noted that

1 https://bitly.cx/1Zuv

Figure 16: Two tested scenarios. The blue square and red rectangles depict the initial positions of the robot and obstacles, respectively.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-4a7bc384-c67e-42cf-adba-aeef6874a10c.jpg)

static obstacles are always guaranteed to be avoided, but collisions between moving obstacles may occur, as no method of reciprocal avoidance is employed.

Many of the obstacles move in almost the same areas, such as humans in a factory, and some obstacles manage to evade the area in which they were initially placed. These areas constitute the so called here dynamic areas, which will be avoided by the global planner for preventing possible disturbance to humans, reduce collision risk, or enforces to surround an area from which the monitoring cannot be correctly achieved due to the presence of people.

Wehave employed two velocities for the dynamic obstacles: ( vr / 3 , ω r / 2) to simulate slow and peaceful obstacle motions and ( vr , ω r ) for fast and aggressive motions.

## 8.1.3. Tested strategies

In order to evaluate the proposed approach, Monitoring Avoiding Dynamic Areas ( MADA ), and elucidate its advantages, we compare the proposed method with two other approaches: a riskier one, Greedy , and another more conservative one, MADP :

- · Greedy . This approach entails the robot selecting the closest point of the frontier between the observed and non-observed regions. There is no an explicit representation of the dynamic areas to be avoided; the robot will navigate among the obstacles, without considering the possibility of loosing monitoring parts of the scenario whilst traverses these areas. It also employs FMM to compute obstacle-free paths and utilizes the path follower to follow them. The wavefront is propagated, surrounding the visible dynamic obstacles and computing the distance gradient from the robot until it reaches the closest non-observed cell, which is established as the next goal. A simple gradient descent from the goal is used to obtain the path. This

(a) Robot following the path

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-2e66a33c-1eda-4ea1-b488-241ef68e5c0d.jpg)

(b) Update of the plan

Figure 17: Mission execution with MADA . In Fig.17(a), the robot follows the initial plan (blue path) to the selected goal. After observing moving obstacles, the robot updates the plan: building dynamic areas (red polygons), recomputing the goal in a new partition to monitor and a new path (blue) to reach it in Fig.17(b).

strategy entails a certain degree of collision risk, mainly in dense areas.

- · Monitoring Avoiding Dynamic Partitions (MADP) . Instead of building dynamic areas when the robot detects moving obstacles in a partition, the entire partition is considered dynamic, allocating a cost to it. The risk of collisions is reduced, but at the cost of entire partitions remaining unobserved. The robot could encircle these areas, resulting in a greater delay in mission time. This approach is a conservative variation of MADA .

With MADA , the robot exhibits a balanced behaviour between the Greedy technique and the more conservative MADP , as illustrated in Fig.17. According with the following evaluation based on the metrics, MADA can monitor most of the scenario, similar to the Greedy approach, reducing the risk of approaching dynamic obstacles and so of the collisions. Additionally, it should achieve this without a substantial increase in distance traveled or mission time, as observed with the conservative MADP approach, which causes longer detours.

In MADP and MADA approaches the robot will decide whether or not to traverse dynamic areas based on a occupancy threshold Oth set by the user. So that, if a unique way to access to a goal is traversing a dynamic area whose obstacle density exceeds the threshold Oth , the goal will be discarded. All partitions corresponding to the branches of the tree traversing these dynamic areas are considered unreachable and discarded as well. Otherwise, if the density is less than Oth , the goal and the partitions are considered reachable. Therefore, the robot will take the risk of traversing the dynamic areas.

## 8.1.4. Metrics

We considered the following metrics: (i) traditional metrics : the total path length traveled by the robot dur- ing the monitoring mission, the total time required by the robot for monitoring, the occurrences of collisions during the mission, and the computation time; (ii) task context metric , such as the ratio of the observed space relative to the free space for different density and velocity of moving obstacles in the scenario; (iii) social behaviors metrics , qualitatively evaluated by means of the distance from the robot to the obstacles, balancing the risk of collision, the space clearance, the path length, and the potential disturbance produced to the moving group. Collisions represent a 'hard' criterion, as a collision equates to a failure and ends the mission. In contrast, the distance to obstacles is a 'soft' criterion, refl ecting how much the robot may disrupt humans moving in the environment.

## 8.2. Simulations

The proposed method was implemented in C++ on the Robotic Operating System (ROS). The simulations were conducted using the Stage simulator on a machine equipped with an Intel Core i7-13700 processor running at 2.1GHz with 16GB of RAM. Multiple simulations were launched, varying the previously described parameters to thoroughly evaluate the performance of the method: strategies ( Greedy , MADA MADP , ), occupancy threshold Oth = [0 , 10 100]%, , safety distance based on the robot radius [ R , 1 5 . R ], two scenarios [Fig.16(a), Fig.16(b)], and the number of obstacles and their velocities, as described in Sect.8.1.1 and 8.1.2.

## 8.2.1. Strategies

Figure 18 shows the overall results of all simulations for the three evaluated strategies in terms of all the metrics de fi ned in Section 8.1.4. Regarding the context of the mission, the main metrics to observe are the % of monitored scenario and of collisions, and the distance to obstacles social metric. The other metrics are not so important in this context, and are a consequence of the decisions made to reach the more relevant metrics.The analysis yielded the following main conclusions, based on the mean, median and quartile values obtained.

- · Regarding Figs. 18(a) and 18(b), we can conclude that MADA is able to monitor a similar percentage of the scenario that Greedy , but with fewer collisions. The MADP method results in a lower number of collisions, but the monitored space is signi fi cantly reduced by approximately 20% because MADP discards entire partitions. MADA is the balanced version, achieving more organized monitoring (thanks to the high-level planner) and avoids obstacle potentially-collision zones.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-7604a801-ff8a-4e6b-a27a-173760ba2623.jpg)

/g0/g1/g2/g2/g3/g4

/g6/g7/g8/g7

/g6/g7/g8/g9

/g5

/g5

/g5

(a) Monitored (%)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-f394ac90-b169-41ef-aae3-c8c8adebd476.jpg)

/g0/g1/g2/g2/g3/g4

/g6/g7/g8/g7

/g6/g7/g8/g9

/g5

/g5

/g5

(c) Distance to obstacles (m)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-52f346b3-2b20-4713-8ce6-1948d858280d.jpg)

/g0/g1/g2/g2/g3/g4

/g6/g7/g8/g7

/g6/g7/g8/g9

/g5

/g5

/g5

/g0/g1/g2/g2/g3/g4

/g6/g7/g8/g7

/g6/g7/g8/g9

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-d7913e95-d59a-407e-ba7e-1269feb33546.jpg)

/g5

/g5

/g5

(b) Collisions (%)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-20bc0d28-6a10-466a-9755-30f16820784d.jpg)

/g0/g1/g2/g2/g3/g4

/g6/g7/g8/g7

/g6/g7/g8/g9

/g5

/g5

/g5

(d) Path length (m)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-608eb57d-e5fb-498b-855f-bde3e1bd7656.jpg)

/g5

/g5

(e)

Mission time (s)

/g5

(f)

Comp. time (s)

Figure 18: Total results based on the employed strategy.

- · Taking into account the distance to obstacle metric, Fig.18(c), MADA lightly increases this distance with respect to Greedy , being bigger for MADP . In Greedy approach, the robot navigates close to the obstacles, increasing the rate of collisions, whilst MADA and MADP try to avoid the areas occupied by moving obstacles, traversing the areas with lower density, therefore reducing the collision risk. Obviously, the distance to obstacles increases with MADP because the robot is enforced to moving away from dense dynamic areas included in the avoided partitions.
- · With MADP and MADA , the robot avoids partitions with moving obstacles, but is enforced to

traverse partitions with lower obstacle density if no path through obstacle-free regions is available, resulting in Greedy -like behavior. Additionally, MADA extends and merges dynamic areas based on obstacle movement. Therefore, in the case of an obstacle moving towards a static or another dynamic obstacle, MADA may obtain paths in the direction of obstacle's movement, causing collisions. This problem has a possible solution, which is presented in Sect.8.3.1.

- · Path length, Fig.18(d), and mission time, Fig.18(e), metrics are related. The robot travels more distance with Greedy and MADA , because with both techniques it monitors most of the scenario. In contrast, with MADP , the robot travels on average 25% less distance than with MADA , leaving regions to be seen, but spending a similar mission time. These classical metrics are not relevant in this mission context, in the case of MADP are a consequence of a lower monitored space than with the other methods.
- · Finally, computation time, Fig.18(f), is lower in Greedy , which does not neither compute dynamic areas nor high and low level plans. However, even in the worst case, any variation of the proposed technique, MADP or MADA , computes the solution in less than 100ms, and can by applied in real time.

Evaluating the results by combining all the metrics allows us to understand the general trend of the proposed MADA method, including both its overall weaknesses and strengths. In the following subsections, we identify the best combination of metrics to be used in real-world experiments, in Section 8.5.

## 8.2.2. Occupancy threshold

The threshold Oth , a parameter of the method, represents a dynamic area density value to decide if a such area can be traversable or not. Three values has been tested: 0%, in which case the area is not traversable; 10%, lower densities allow to traverse the area navigating the robot among the obstacles; 100%, the area is traversable, it is not avoided by the planner.

Based on the results of monitoring, Fig.19(a), and collisions, Fig.19(b), it is better to use MADA or MADP with Oth = 10%, because both approaches achieve a good balance between monitored part of the scenario and with lower number of collisions than Greedy .

When the occupancy threshold is not zero, MADA shows no signi fi cant difference in the monitored area,

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-b3169d4a-1ace-4177-a0f3-b04d3dcff271.jpg)

/g5

/g5/g9/g10/g5

/g5/g11/g9/g10/g5

/g5/g11/g9/g9/g10/g5

/g5/g9/g10/g5

/g5/g11/g9/g10/g5

/g5/g11/g9/g9/g10/g5

(a) Monitored (%)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-316ca667-f393-46b1-8bc7-2d00e75f12d3.jpg)

/g5

/g5/g9/g10/g5

/g5/g11/g9/g10/g5

/g5/g11/g9/g9/g10/g5

/g5/g9/g10/g5

/g5/g11/g9/g10/g5

/g5/g11/g9/g9/g10/g5

(b) Collisions (%)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-26d9057b-02fe-46b5-84c3-dadcce717f47.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-2ae72aa1-56b4-4361-a599-5e6c51aac5a3.jpg)

/g11/g9

(d)

Distance to obstacles (m)

Figure 19: Results based on the occupancy threshold.

collisions, or distance to obstacles. This is because rapid expansion of dynamic areas due to obstacle movement quickly reduces density, making areas more traversable and prioritizing less dense ones.

When Oth &gt; 0%, it does not affect the computation time, Fig.19(c), because the costly part is the construction of the area itself more than the processing of the density.

## 8.2.3. Safety distance

Asafety distance is added to the obstacles and the dynamic areas to enlarge them, increasing the safety distance from robot to obstacles. As can be seen in Fig.20, the monitored area is increased and collisions are reduced with the in fl ation. However, MADA keeps the best balance for both metrics, signi fi cantly increasing the monitored space (10%), but strongly reducing the rate of collisions (35%).

## 8.2.4. Handling of dynamic areas

In this section, we have evaluated four different ways the robot handles information when it sees again the previously constructed dynamic areas: (i) memorize everything, including both the points of the trajectories and the areas constructed from them; (ii) keep the points, but forget the areas if there is no obstacle inside when are seen by the robot (if there is an obstacle inside, the area is restored); (iii) forget everything, both points and areas, if there are no observed obstacles inside them within the visibility range; (iv) forget the areas in LoS (Line-of-Sight), but keep the areas that are

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-21edb12c-5227-4829-b524-b15508beeccc.jpg)

/g0/g1/g2/g2/g3/g4

/g5

/g0/g1/g2/g2/g3/g4

/g6/g7/g8/g9

/g0/g1/g2/g2/g3/g4

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-25d1c4e0-68c0-4f6a-8eb9-1794b93dbbcb.jpg)

/g5

/g5

(a) Safety distance: R .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-d1b8e9fb-6f09-4cad-9319-5472c11deb7e.jpg)

/g5

/g6/g7/g8/g7

/g5

/g6/g7/g8/g7

/g5

/g6/g7/g8/g9

/g0/g1/g2/g2/g3/g4

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-19effdec-4884-48f7-9bb1-f832722c12f3.jpg)

/g5

/g5

/g6/g7/g8/g7

/g5

/g6/g7/g8/g7

/g5

(b) Safety distance: 1 5 . R .

Figure 20: Results for different safety distances.

not seen, having a Greedy behaviour in LoS.

This way we obtain different behaviours of the global planner. (i) and (ii) keep track of the detected dynamic areas, to take them into account for a further replanning; the fi rst one keeping the whole areas, the second one leaving more room for re-planning, but being aware that in these areas were occupied by moving obstacles. On the contrary, (iii) and (iv) forget the whole information of the dynamic areas detected when they are not seen, leaving more space for re-planning when needed; building and using the fi rst one the dynamic areas for planning paths, and using a greedy technique for navigation among the obstacles. We aim to determine what is the best one in terms of the de fi ned metrics.

The results are shown in Fig.21. Again, MADA and MADP outperform the Greedy approach in the ratio of collisions and monitored space. MADA improves the monitored area against MADP .

Regarding MADA , (ii) and (iv) strategies are the best; it is advantageous to keep storing trajectories and forgetting areas when the robot sees no obstacle in the area, or forgetting them when they are in LoS. This behaviors achieve the best ratio of monitoring and collisions, outperforming both Greedy and MADP . The robot effectively monitors the environment while avoiding situations where obstacles push it towards walls, thus re-

/g6/g7/g8/g9

/g5

/g6/g7/g8/g9

/g5

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-9593e487-4391-4b29-8cd1-12ea16521284.jpg)

(a) Monitored (%)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-1a854d55-561c-4a49-8584-127a9477c5ff.jpg)

Figure 21: Results based on the handling of the information of the dynamic areas.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-021ee905-6ed9-49e8-bd40-7a778cf760bd.jpg)

/g5/g6/g7/g2/g8/g5/g9/g5

/g5/g6/g7/g2/g8/g5/g10/g5

/g5/g6/g7/g2/g8/g5/g9/g5

/g5/g6/g7/g2/g8/g5/g10/g5

/g5/g6/g7/g2/g8/g5/g9/g5

/g5/g6/g7/g2/g8/g5/g10/g5

(a)

Monitored (%)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-0089918e-e98f-46a7-9c70-2cef9381cc2e.jpg)

(b)

Collisions (%)

Figure 22: Results based on the scenario.

ducing collisions.

## 8.2.5. Scenarios

The Fig.22 presents the results for the tested techniques in both scenarios, described in Sect.8.1.1. The rate of collisions is higher and the monitored scenario lower for all the methods in the second scenario. This is more challenging for monitoring missions due to its large stretch corridor and wide open spaces where dy-

Figure 23: Results based on the velocity of the obstacles.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-9d73eca2-cb2c-40c7-bcb7-2191cb262f8d.jpg)

Figure 24: Results based on the number of obstacles.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-2cd5e323-bd1b-432c-97a0-3134f0eadb77.jpg)

namic obstacles can freely move.

Computational time is higher in the second scenario, because of its size. But all strategies remain within the 100ms threshold, considered real-time. This is because the high-level planner selects the closest goals, and the low-level planner expands the FMM wavefront only to these goals.

## 8.2.6. Velocity of obstacles

Across all methods, it is observed that as obstacles move faster, more space is effectively monitored and fewer collisions occur, see Fig.23. This outcome is primarily in fl uenced by the nature of the obstacle movement rather than the methods themselves. These movements, characterized by sudden changes from stationary to movement, pose challenges in prediction. These complexities are highlighted and better illustrated in the video.

## 8.2.7. Number of obstacles

The number of obstacles determines the density of environment where the robot is monitoring: dense and non-dense environments. We illustrate the results for both densities in Fig.24. As expected, the denser the environment, the less it can be monitored and the more collisions occur. MADP results in very few collisions, especially in low-density environments, but it typically

Figure 25: Results adding the projections of future positions of the obstacles. The strategies with the projections are denoted with ∗ .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-f7fdd5ed-0bf5-41c7-b7ac-dc0e8786ece1.jpg)

monitors less than 50% of the scenario, as it avoids and discards many regions. On the other hand, MADA has a higher collision rate, but it consistently manages to monitor nearly 60% of the scenario in non-dense environments.

## 8.3. Modularity for extensions

We aim to highlight the modularity of the proposed method, highlighting how easily new modules can be integrated or existing ones replaced at any stage of the diagram shown in Fig.3 of the Section 4.

Aclear example of this modularity is seen in the techniques evaluated in the present work. The complete technique proposed is MADA , but in fact Greedy and MADP exemplify the modular nature of the method. Greedy does not use the high-level planner or the construction of dynamic areas. Meanwhile, MADP , is exactly identical to MADA except for using a different approach to construct dynamic areas.

## 8.3.1. Projection of future obstacle movements

As previously described, one of the problems we encountered is when a dynamic obstacle creates a dynamic area, pushing the robot into a wall as it tries to navigate through free space. A simple solution implemented here is to predict future positions based on the velocity of the obstacles detected by the robot, adding greater safety. This module is inserted right before the low-level planner in Fig.3.

The results of the different strategies are illustrated in Fig.25. There is a signi fi cant improvement for all three techniques. All of them reduce the number of collisions by 50% compared to the techniques without projections. The improvement is even more signi fi cant for MADA versus MADA ∗ . It comes at the cost of exploring an average of 10% less of the scenario compared to the version without projections. It is arguably advantageous to add such predictions. More complex prediction methods could be implemented, but they are out of the scope of this work. The objective was to analyse how taking into account the future position of the obstacles using a simple technique, in fl uence the metrics.

## 8.3.2. Other planners

In this work, we have presented a global planning technique for dynamic environments. We assessed our method with and without using the high-level planner, greedy and MADA in the Fig.26, respectively. We do not evaluate reactive navigators alone for maneuvering among obstacles. Instead, we evaluate and compare our proposal with other well-established state-of-the-art global planners integrated with different reactive planners. We assessed our method, by replacing different parts of the low-level planner:

- · Using the move base node 2 (mb in the results). This node handles everything. The high-level planner sends the goal, and move base proceeds to plan the path using Dijkstra and generates the appropriate speed commands to follow it using the Dynamic Window Approach (DWA)[40].
- · Dijkstra+DWA(dd in the results). Similar to the move base node, but we update the costmaps and plan with Dijkstra and DWA by ourselves, instead of move base , generating the optimal path and the best speed command at each instant.
- · FMM+DWA(fdintheresults). Uses our path planner (FMM) to generate paths that avoid dynamic areas and employs DWA to follow the path.
- · The MADA approach FMM+path follower (fp in the results). Uses FMM for path planning avoiding dynamic areas and our path follower for execution.

Aqualitative advantage of our methods is the absence of parameters requiring adjustment for operation. The only user-set value is the occupancy threshold, which determines obstacle density for traversable dynamic areas. Except for this parameter, the planners self-adjust according to the environment, considering the robot's size and distance to obstacles.

Regarding quantitative values, shown in Fig.26:

- · Using move base is not effective, as it does not control the planning process, causing the robot to get stuck and fail to explore over 50% of the scenario, despite having the fewest collisions.

2 http://wiki.ros.org/move\_base

Figure 26: Results based on the employed planners.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-a9b33bd2-c7cf-42cf-9dee-11133de85c28.jpg)

- · The Dijkstra+DWA combination results in aggressive behavior with high speeds, leading to many collisions due to overlooked dynamic areas.
- · Our path planner MADA improves the results. Both the method with the path-follower (fp) and its version with DWA (fd) achieve a better balance between scenario monitoring and collisions. FMM + path follower outperforms FMM + DWA with Greedy , monitoring 5% less but with 30% fewer collisions. Incorporating dynamic area construction and avoidance, FMM+DWA collides 15% less, and FMM+path follower monitors almost 10% more. This shows that once dynamic areas are identi fi ed, DWA reacts better to sudden movements, avoiding collisions.

This evaluation concludes that: (i) a global planner for dynamic environments is essential, regardless of the integrated local planner or reactive navigator; (ii) a good local planner integrated with the global planner for dynamic scenarios improves the whole system. A standalone local planner, even if tailored for dynamic environments, is insuf fi cient for optimizing or adapting to speci fi c missions, as correct subgoal selection and handling dynamic areas are crucial for mission success.

## 8.4. Comparison with other methods

In this section we have compared the proposed method MADA with other state-of-the-art approaches in the monitoring mission. The fi rst, is a method of avoidance of crowded regions. The second, is a social path planner employed in monitoring missions altogether with the dynamic region avoidance, proposed in this work.

## 8.4.1. Crowded regions avoidance

As discussed in Section 2, most methods there mentioned focus on navigation or path planning in human environments. In [21], the authors propose the CrowdBased Dynamic Blockages ( CBDB ) layer, which shares

Figure 27: Comparison with a method for crowded region avoidance.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-51045afc-d273-49bf-ab03-f64ab1f66ec8.jpg)

similarities with our approach by avoiding crowded regions that hinder navigation due to obstacle density. Using the CBDB layer, the robot evaluates potential paths and selects between navigating through or around obstaclefi lled areas. This method resembles our MADP approach, where large regions are considered occupied or not based on a threshold. Thus, we compare the CBDB approach with our MADA method, which dynamically adjusts dynamic areas based on obstacle movement. The high-level planner generates a goal from which the robot makes the next observation. Then, the CBDB layer is applied to de fi ne and evaluate the regions with possible blockages. For a fair comparison, we use FMM to compute the path, instead of A* used in [21], in order to maintain the robot far away from static obstacles and maximize the fi eld of view, as explained in previous sections. And both strategies use DWA for navigation. The comparison focuses on how dynamic areas are handled. With CBDB , large regions around moving people are blocked, while with MADA , the areas are adjusted to the actual space occupied by obstacles, allowing more space for navigation. Simulations were conducted in the scenarios shown in Fig.16, with results illustrated in Fig.27.

As shown in Fig.27(a), the robot monitors a larger portion of the environment using MADA compared to

CBDB . This is because, despite moving closer to dynamic obstacles (Fig.27(c)), MADA results in fewer collisions, in Fig.27(b). This suggests that considering large regions, especially in environments with dispersed obstacles, is less effective when all paths cross obstacle-dense areas. Instead, MADA creates regions that adapt to the observed movement of dynamic obstacles, allowing the robot to navigate through obstaclefree gaps and avoid collisions. In Fig.27(b), the difference in collisions is smaller in the second scenario due to its corridor-like structure, with fewer path options. This structure also affects computation time, in Fig.27(d), as CBDB evaluates fewer paths, leading to a faster computation than MADA . However, in the fi rst scenario, with more bifurcations, CBDB takes slightly longer than MADA to compute the best path.

In conclusion, CBDB offers computational time savings in simpler environments with few bifurcations. However, in more complex environments with many corridors and rooms, MADA performs similarly in terms of time, and its dynamic region adaptation allows for collision-free paths by leveraging the movement of obstacles in more spacious areas.

## 8.4.2. Social path planning

In this section, we demonstrate the bene fi ts of integrating dynamic area information with social path planners. Speci fi cally, we incorporate the social path planner from [16] (referred to as SFMM) into our global planner for monitoring missions involving dynamic obstacles. SFMM employs the Fast Marching Method (FMM) for social path planning in environments with humans. It incorporates a prede fi ned social space , based on [41], using a Gaussian mixture model in the velocity map to generate a gradient that repels the robot's path away from people. SFMM is applied in various scenarios, such as navigating toward speci fi c goals while avoiding humans, or interacting with individuals or groups. Our focus is on the former: a robot navigating through shared spaces with individual people.

We chose this planner for comparison due to its similarities with our approach. First, it is based on FMM, making integration into our method straightforward. Second, SFMM ensures safe trajectories by maintaining a safe distance from obstacles. However, there are two key differences from our proposed approach. SFMM trims the velocity map generated by static obstacles to maintain a certain degree of safety, without diverting the path too far from the optimal route to the goal. In contrast, our approach maximizes safety by keeping the paths as far from obstacles as possible, enhancing the robot's fi eld of view for better monitoring. Additionally,

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-1de022ae-5cc1-40b5-8a48-e6f85f67d0d9.jpg)

/g0/g1/g2/g3/g0/g0

/g0/g5/g6/g5

/g0/g5/g6/g5/g1/g2/g3/g0/g0

/g4

/g4

/g4

(a) Monitored (%)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-1138fce3-ae75-4537-bf0d-29c359f13524.jpg)

/g4

/g4

/g4

(c)

Mission time (s)

/g0/g1/g2/g3/g0/g0

/g0/g5/g6/g5

/g0/g5/g6/g5/g1/g2/g3/g0/g0

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-b6559f39-4779-4308-81a8-deb206830f12.jpg)

/g4

/g4

/g4

(b) Collisions (%)

Figure 28: Comparison with a social planning method.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-701fbd86-70f7-4894-9740-5ba4270e769c.jpg)

we incorporate dynamic areas, which represent regions where obstacles are in motion.

Thus, we incorporated the SFMM planner into our approach to assess whether including dynamic areas offers advantages. Simulations were run in a highobstacle-density scenario of Fig.16(a). For a fair comparison, all planners use DWA to navigate. The simulation results are presented in Fig.28. As before, the highlevel planner, described in Section7.1, is responsible for generating monitoring goals, and the path planner computes the path to reach these goals. We compared the SFMM with and without dynamic areas, referred to as M-SFMM and MADA-SFMM, respectively, in the results. As shown in Fig.28(a), with M-SFMM, the robot monitored between 50% and 85% of the scenario in most trials. Using MADA , this ratio increased to 60-93%. When both methods were combined MADASFMM, that is the management of dynamic areas and the Gaussian-based model for the moving people, the ratio improved further, reaching 65-90%. This improvement improvement was directly related to the collision rates, Fig.28(b). With M-SFMM alone, despite avoiding social spaces of the obstacles, the robot collided in 50% of the trials, due to navigating through crowded regions. With MADA, collisions were reduced to 40%, as the planner guided the robot through less crowded areas.

However, in densely populated environments like ours, it is nearly impossible to fi nd completely obstacle-free zones, which explains the remaining collisions. The best performance was achieved by combining both techniques, MADA-SFMM, reducing collisions to just 20%. This improvement was due to the dynamic area information being incorporated into the velocity map to compute the gradient, as described in eq.6 of Section 7.2.2, while SFMM kept the path away from obstacles within the dynamic areas, increasing safety by adding the social space buffer around the obstacles.

In terms of mission time, in Fig.28(c), we observe that while M-SFMM is more risky, navigating through denser areas allows it to complete the mission more quickly, ranging 40-140s in most trials. On the other hand, MADA , takes longer - up to 85 to 235 seconds -duetotaking greater detours to enhance safety. However, combining both methods with MADA-SFMM reduces the mission time to 70-170 seconds. This occurs because the planner includes the social space around obstacles, balancing safety with ef fi ciency. MADASFMM offers the best of both worlds: it is safer, monitors more effectively, and completes the mission faster, with the trade-off being slightly increased computation time, as depicted in Fig.28(d).

In conclusion, planning global paths by explicitly managing dynamic area avoidance with MADA proves to be more practical than focusing on individual obstacle avoidance in such obstacle-dense environments. Incorporating dynamic area information, as proposed in our work, alongside other social planners signi fi cantly improves the path-planning process in terms of safety when the robot is forced to navigate regions shared with dynamic obstacles. Additionally, this highlights the modularity of our approach, which can easily integrate other path planners.

## 8.5. Real-world experimentation

The proposed approach was tested in the hall of the Ada Byron building at the University of Zaragoza. An example of the execution of the mission is available in the video . 3 The experiments were conducted using a Turtlebot equipped with a Hokuyo lidar (20m range, 180º fi eld of view) and a camera for scenario monitoring, with a imposed visibility range set to vr = 5m. That is, the robot registers from the LiDAR dynamic obstacles up to 20m away, but needs to approach within 5 meters to correctly monitor the scene. The robot is localized with AMCL, and only observed dynamic obstacles are depicted on the known static map, illustrated with black dots in the video. Initially placed in the middle of the hall, the robot monitored the entire environment.

The entrance to the building is on the left side of the scenario, resulting in higher dynamism in that region. As shown in the videos, the robot encounters the most dif fi culty navigating there. Based on simulated results, we set the best combination of parameters: Oth = 10%, safety distance 1 5 . R , and memorizing obstacle trajectories but forgetting them when no obstacles are inside, the (ii) mode explained in Section 8.2.4. Four realworld experiments were conducted, resembling simulations: dense and non-dense environments, and with slow and fast human movements.

As seen in the video, people usually avoid collisions with the robot. When they move much faster than the robot, as in the fi rst experiment, it is impossible for the robot to avoid disturbing them completely. Fast foot movements also complicate building dynamic areas, which is a problem we will address in the near future. However, as illustrated in Fig.29, the robot successfully completed the mission by navigating around areas with a high presence of dynamic obstacles whenever possible.

With slower human movements, the robot can better build dynamic areas, as seen in the video. This allows it to navigate around these areas more effectively and avoid disturbing people. The robot also chooses different directions, regions to monitor and plans different paths based on the observed dynamism. This is clearly seen in the third and fourth experiments, Nondense/Slow and Dense/Slow respectively, where the planner selects opposite monitoring directions.

The code used for this research will be made available upon publication acceptance. This will enable researchers to reproduce the results and facilitate further development in this fi eld.

## 9. Conclusions

In this paper, we have presented a method for global planning and navigation in the presence of moving obstacles, tailored for monitoring mission contexts. The proposed approach MADA involves the robot constructing dynamic areas where obstacles are moving, avoiding areas considered dense based on their occupation. The method was evaluated by comparing it with two other approaches: a Greedy strategy and a more conservative version of the proposed method, MADP , which avoids larger spaces with moving obstacles rather than building dynamic areas around them. The results show that the proposed technique achieves a good balance between

3 https://bitly.cx/1Zuv

Figure 29: The robot accomplished the monitoring mission, traveling the path depicted by the gray line while avoiding regions with high occupancy of dynamic obstacles. The trajectories of people, registered by the robot (during the whole mission), are shown as red points, and the dynamic areas (at the end of the mission) are illustrated with red polygons.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00846v2-figure-4547daf8-06ac-4a8d-b46b-15829dd9484c.jpg)

the monitored portion of the scenario, the time to complete the mission, whilst avoiding regions more densely occupied by moving obstacles to reduce the risk of collision. MADA , by constructing dynamic areas that are adjusted to the observed obstacle movement, proves to be more ef fi cient than other techniques that either build larger regions based on the environment or directly adjust to each individual obstacle using a social model. We have shown the modularity of the proposed method, which is advantageous for extensions of the method. The evaluation of the results reveals that a global mission planner which integrates dynamic global trajectory planner and local planners improves the performance in terms of safety and social criteria associated to a speci fi c mission.

The method can potentially be extended or adapted for use in other common robotic problems or applications different to monitoring, such as classical coverage problems or object-seeking tasks in scenarios with dynamic obstacles, only modifying the High-level planner for a context-aware execution. A potential future research direction is the extension of our method to multirobot teams, introducing challenges related to partitioning and goal allocation among robots.

## Acknowledgments

This work was partially supported by the Spanish projects PID2022-139615OBI00/MCIN/AEI/10.13039/501100011033/FEDER-UE and Aragon Government FSE-T45 23R.

## Declaration of generative AI and AI-assisted technologies in the writing process

During the preparation of this work the authors used Gemini in order to improve text readability. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the content of the published article.

## References

- [1] E. Galceran, M. Carreras, A survey on coverage path planning for robotics, Robotics and Autonomous Systems 61 (12) (2013) 1258 - 1276. doi:https://doi.org/10.1016/ j.robot.2013.09.004 .
- [2] D. Mitchell, M. Corah, N. Chakraborty, K. Sycara, N. Michael, Multi-robot long-term persistent coverage with fuel constrained robots, in: 2015 IEEE International Conference on Robotics and Automation (ICRA), 2015, pp. 1093-1099.
- [3] C. S. Tan, R. Mohd-Mokhtar, M. R. Arshad, A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms, IEEE Access 9 (2021) 119310-119342.
- [4] A. Farinelli, L. Iocchi, D. Nardi, Distributed on-line dynamic task assignment for multi-robot patrolling, Autonomous Robots 41 (6) (2017) 1321-1345.
- [5] N. Agmon, S. Kraus, G. A. Kaminka, Multi-robot perimeter patrol in adversarial settings, in: 2008 IEEE International Conference on Robotics and Automation, 2008, pp. 2339-2345.
- [6] D. Kingston, R. W. Beard, R. S. Holt, Decentralized perimeter surveillance using a team of uavs, IEEE Transactions on Robotics 24 (6) (2008) 1394-1404.
- [7] S. Bernardini, M. Fox, D. Long, Planning the behaviour of lowcost quadcopters for surveillance missions, International Conference on Automated Planning and Scheduling (2014).
- [8] C. Craye, D. Filliat, J. Goudou, Environment exploration for object-based visual saliency learning, in: 2016 IEEE International Conference on Robotics and Automation (ICRA), 2016, pp. 2303-2309.
- [9] R. G. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, S. Thrun, H. L. S. Younes, Coordination for multi-robot exploration and mapping, in: Proceedings of the Seventeenth National Conference on Arti fi cial Intelligence and Twelfth Conference on Innovative Applications of Arti fi cial Intelligence, AAAI Press, 2000, p. 852-858.
- [10] A. Francis, C. P´ erez-D'Arpino, C. Li, F. Xia, A. Alahi, R. Alami, A. Bera, A. Biswas, J. Biswas, R. Chandra, H.-T. L. Chiang, M. Everett, S. Ha, J. Hart, J. P. How, H. Karnan, T.W. E. Lee, L. J. Manso, R. Mirksy, S. Pirk, P. T. Singamaneni, P. Stone, A. V. Taylor, P. Trautman, N. Tsoi, M. V´ azquez, X. Xiao, P. Xu, N. Yokoyama, A. Toshev, R. Mart´n-Mart´n, ı ı Principles and guidelines for evaluating social robot navigation algorithms (2023). arXiv:2306.16740 .

URL https://arxiv.org/abs/2306.16740

- [11] A. Biswas, A. Wang, G. Silvera, A. Steinfeld, H. Admoni, Socnavbench: A grounded simulation testing framework for evaluating social navigation, Trans. Human-Robot Interaction 11 (3) (July 2022).

| [12]   | M. C. Shrestha, Y. Nohisa, A. Schmitz, S. Hayakawa, E. Uno, Y. Yokoyama, H. Yanagawa, K. Or, S. Sugano, Us- ing contact-based inducement for ef fi cient navigation in a con- gested environment, in: 2015 24th IEEE International Sympo- sium on Robot and Human Interactive Communication (RO- MAN), 2015, pp. 456-461. doi:10.1109/ROMAN.2015. 7333673 .   |
|--------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [13]   | C. Chen, Y. Liu, S. Kreiss, A. Alahi, Crowd-robot interac- tion: Crowd-aware robot navigation with attention-based deep reinforcement learning, in: 2019 International Conference on Robotics and Automation (ICRA), 2019, pp. 6015-6022. doi: 10.1109/ICRA.2019.8794134 .                                                                                    |
| [14]   | L. M. N. P´rez, e Fernando Caballero, Teaching robot navigation behaviors to optimal rrt planners, International Journal of Social Robotics 10 (2) (2018) 235 - 249.                                                                                                                                                                                          |
| [15]   | P. Teja S., R. Alami, Hateb-2: Reactive planning and decision making in human-robot co-navigation, in: 2020 29th IEEE In- ternational Conference on Robot and Human Interactive Com- munication (RO-MAN), 2020, pp. 179-186. doi:10.1109/ RO-MAN47096.2020.9223463 .                                                                                          |
| [16]   | J. V. G´mez, o N. Mavridis, S. Garrido, Fast marching solution for the social path planning problem, in: 2014 IEEE Interna- tional Conference on Robotics and Automation (ICRA), 2014, pp. 1871-1876. doi:10.1109/ICRA.2014.6907105 .                                                                                                                         |
| [17]   | S. Forer, S. B. Banisetty, L. Yliniemi, M. Nicolescu, D. Feil- Seifer, Socially-aware navigation using non-linear multi- objective optimization, in: 2018 IEEE/RSJ International Con- ference on Intelligent Robots and Systems (IROS), 2018, pp. 1-9. doi:10.1109/IROS.2018.8593825 .                                                                        |
| [18]   | M. Kollmitz, K. Hsiao, J. Gaa, W. Burgard, Time depen- dent planning on a layered social cost map for human-aware robot navigation, in: 2015 European Conference on Mobile Robots (ECMR), 2015, pp. 1-6. doi:10.1109/ECMR. 2015.7324184 .                                                                                                                     |
| [19]   | M.-T. Lorente, L. Montano, Robot navigation balancing safety and time to goal in dynamic environments, in: 2017 European Conference on Mobile Robots (ECMR), 2017, pp. 1-8. doi:                                                                                                                                                                              |
| [20]   | 10.1109/ECMR.2017.8098683 . Z. Talebpour, D. Viswanathan, R. Ventura, G. Englebienne, A. Martinoli, Incorporating perception uncertainty in human- aware navigation: A comparative study, in: 2016 25th IEEE In- ternational Symposium on Robot and Human Interactive Com- munication (RO-MAN), 2016, pp. 570-577. doi:10.1109/ ROMAN.2016.7745175 .          |
| [21]   | A. Deus, G. Daudt, R. Maffei, M. Kolberg, Mapping crowd- based dynamic blockages for navigation in indoor environments, in: 2023 IEEE 19th International Conference on Automation Science and Engineering (CASE), 2023, pp. 1-6. doi:10. 1109/CASE56687.2023.10260430 .                                                                                       |
| [22]   | J. A. Sethian, A fast marching level set method for monotoni- cally advancing fronts, Proceedings of the National Academy of Sciences of the United States of America 93 (4) (1996) 1591- 1595.                                                                                                                                                               |
| [23]   | N. M. Amato, Y. Wu, A randomized roadmap method for path and manipulation planning, in: Proceedings of IEEE Interna- tional Conference on Robotics and Automation, Vol. 1, 1996, pp. 113-120 vol.1.                                                                                                                                                           |
| [24]   | S. M. Lavalle, Rapidly-exploring random trees: A new tool for path planning, Tech. rep., Department of Computer Science, Iowa State University (1998).                                                                                                                                                                                                        |
| [25]   | S. Karaman, E. Frazzoli, Sampling-based algorithms for optimal motion planning, The International Journal of                                                                                                                                                                                                                                                  |

|      | Robotics Research 30 (7) (2011) 846-894. doi:10.1177/                                                                                                                                                                                                                                                                          |
|------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [26] | J. D. Gammell, S. S. Srinivasa, T. D. Barfoot, Informed rrt*: Op- timal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic, in: 2014 IEEE/RSJ Inter- national Conference on Intelligent Robots and Systems, 2014, pp. 2997-3004. doi:10.1109/IROS.2014.6942976 .                  |
| [27] | J. D. Gammell, T. D. Barfoot, S. S. Srinivasa, Batch informed trees (bit*): Informed asymptotically optimal anytime search, The International Journal of Robotics Research 39 (5) (2020) 543-567. doi:10.1177/0278364919890396 .                                                                                               |
| [28] | P. E. Hart, N. J. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transac- tions on Systems Science and Cybernetics 4 (2) (1968) 100-107.                                                                                                                                      |
| [29] | L. Fermin-Leon, J. Neira, J. A. Castellanos, Incremental contour-based topological segmentation for robot exploration, in: 2017 IEEE International Conference on Robotics and Au- tomation (ICRA), 2017, pp. 2554-2561.                                                                                                        |
| [30] | A. Kleiner, R. Baravalle, A. Kolling, P. Pilotti, M. Munich, A solution to room-by-room coverage for autonomous clean- ing robots, in: 2017 IEEE/RSJ International Conference on In- telligent Robots and Systems (IROS), 2017, pp. 5346-5352.                                                                                 |
| [31] | Voronoi Diagrams, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 147-171. doi:10.1007/ 978-3-540-77974-2_7 . https://doi.org/10.1007/                                                                                                                                                                               |
|      | URL                                                                                                                                                                                                                                                                                                                            |
| [32] | E. W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1) (1959) 269-271.                                                                                                                                                                                                                            |
| [33] | M. Andriluka, S. Roth, B. Schiele, People-tracking-by-detection and people-detection-by-tracking, in: 2008 IEEE Conference on Computer Vision and Pattern Recognition, 2008, pp. 1-8.                                                                                                                                          |
| [34] | D. Ramanan, D. A. Forsyth, A. Zisserman, Tracking people by learning their appearance, IEEE Transactions on Pattern Analy- sis and Machine Intelligence 29 (1) (2007) 65-81.                                                                                                                                                   |
| [35] | C. Bregler, J. Malik, Tracking people with twists and expo- nential maps, in: Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231), 1998, pp. 8-15.                                                                                                               |
| [36] | P. Fiorini, Z. Shiller, Motion planning in dynamic environ- ments using velocity obstacles, The International Journal of Robotics Research 17 (7) (1998) 760-772. doi:10.1177/ 027836499801700706 .                                                                                                                            |
| [37] | T. Fraichard, H. Asama, Inevitable collision states. a step to- wards safer robots?, in: Proceedings 2003 IEEE/RSJ Interna- tional Conference on Intelligent Robots and Systems (IROS 2003) (Cat. No.03CH37453), Vol. 1, 2003, pp. 388-393 vol.1.                                                                              |
| [38] | M.-T. Lorente, E. Owen, L. Montano, Model-based robocentric planning and navigation for dynamic environments, The Inter- national Journal of Robotics Research 37 (8) (2018) 867-889. doi:10.1177/0278364918775520 .                                                                                                           |
| [39] | V. Gonz´lez, a C. A. Monje, L. Moreno, C. Balaguer, Fast march- ing square method for uavs mission planning with considera- tion of dubins model constraints, IFAC-PapersOnLine 49 (17) (2016) 164 - 169, 20th IFAC Symposium on Automatic Con- trol in AerospaceACA 2016. doi:https://doi.org/10. 1016/j.ifacol.2016.09.029 . |
| [40] | D. Fox, W. Burgard, S. Thrun, The dynamic window approach to collision avoidance, Vol. 4, 1997, pp. 23-33.                                                                                                                                                                                                                     |
| [41] | E. T. Hall, The hidden dimension: Man's use of space in public and private, The Bodley Head Ltd, London (1990).                                                                                                                                                                                                                |
Yaroslav Marchukov Luis Montano
Occupation-aware planning method for robotic monitoring missions in dynamic environments
This paper presents a method for robotic monitoring missions in the presence
of moving obstacles. Although the scenario map is known, the robot lacks
information about the movement of dynamic obstacles during the monitoring
mission. Numerous local planners have been developed in recent years for
navigating highly dynamic environments. However, the absence of a global
planner for these environments can result in unavoidable collisions or the
inability to successfully complete missions in densely populated areas, such as
a scenario monitoring in our case. This work addresses the development and
evaluation of a global planner, $MADA$ (Monitoring Avoiding Dynamic Areas),
aimed at enhancing the deployment of robots in such challenging conditions. The
robot plans and executes the mission using the proposed two-step approach. The
first step involves selecting the observation goal based on the environment's
distribution and estimated monitoring costs. In the second step, the robot
identifies areas with moving obstacles and obtains paths avoiding densely
occupied dynamic regions based on their occupation. Quantitative and
qualitative results based on simulations and on real-world experimentation,
confirm that the proposed method allows the robot to effectively monitor most
of the environment while avoiding densely occupied dynamic areas.