1 of 15

D-Planner: An Efficient Surrounding-Aware Multi-Drone System for Urban Monitoring

Paper #1571036031

�

Tianhao Yu, Matthew Caesar, Shadman Saqib Eusuf

University of Illinois Urbana-Champaign

2 of 15

Urban warfare is hard

Urban terrain contains dense 3D infrastructures
Line of sight is poor
Tactics can give upper-hand (e.g., ambushing, sniping)
Civilians should be unharmed

Gather intelligence on enemy location, ammunition etc.
Create a 3D terrain map

Why is it hard?

How to plan effectively?

What is needed for planning?

Real-time data from data sites across the city

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

Urban warfare can be challenging. There are many reasons behind this.

The terrain in much more complex than other environments. There are dense three dimensional infrastructure like residential buildings, skyscrapers, factories, sewers , tunnels, fly-overs, and so on. Often there are internal and external spaces, for example, the enemy can be hiding behind a building or inside a room. Also typically underground roads or subways can help enemies move unnoticed.

Besides, because of the buildings, boundary walls, and a large number vehicles, the line of sight is often relatively lower.

This can give the enemy tactical advantages specially if they adopt strategies like ambushing or having snipers located at tall buildings. So even if they are outnumbered in terms of armor or ammunition, they can still have an advantage.

The situation gets complicated because of the presence of civilians since we do not want to harm them. Enemy combatants can even try to use them as human shields or can be in disguise of civilians.

All these and many more reasons adds complexity to urban battles. So it is important to gather intelligence on enemy’s location, ammunition and the overall terrain to plan effective missions against them while minimizing the collateral damage. Thus, gathering data from different sites spread across the entire city can help a lot with the plans.

3 of 15

How can we collect the data?

Human warfighter observers?

Risk, inefficiency, manual labor�

Smart devices/infrastructures?

Automatic, but connectivity issues, limited range

Better solution: Drones with sensors

Can carry out complex mission
Extensive range, can be networked together

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

So if the data sites like enemy’s hideouts, ammunition, traps, friendly forces, civilians are spread out across the city, how can we collect the data?

One option would be to install human warfighter observers. But that is often very risky, inefficient and requires manual labor, if at all possible.

Another option could be to use smart devices or infrastructure apriori. It would be automatic, but that is not always realistic. Besides, in times of war, they can be disconnected for power outage, limited range etc.

A better solution may be to rely on air surveillance using drones with sensors. This is because they can carry out complex missions, cover extensive ranges and can be networked together.

For example, if we have some drones with cameras, they can visit different data sites, capture images, and send them over the network, providing with real time data.

4 of 15

Challenges in drone navigation

Can cover only a certain distance i.e., a limited number of data sites

Need to avoid both moving (vehicles, people) & stationary obstacles (buildings, walls etc.)

Should coordinate to ensure different drones visit different data sites

Should be able to alter path based on dynamic priority of the data sites (i.e, visit if more valuable than initially assessed and avoid if dangerous)

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

5 of 15

Problem decomposition

Sub-problem	Given	Goal
Global waypoint planning	Data site locations, their values, and power budgets of the drones	Find the path/trajectory of the drones, cumulatively containing the highest value of data
Real-time obstacle avoidance	The current location & observations of the surroundings and the next data site location on the waypoint trajectory of a drone	Navigate avoiding obstacles
Dynamic path recomputation	Initially planned path of a drone, updated values of the data sites	Dynamically change the path to include new data sites or exclude potentially dangerous data sites

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

6 of 15

Modular architecture

Global waypoint planning module

Incremental path recomputation module

Obstacle avoidance module

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

So we have designed a modular architecture to solve the different sub-problems.

First, in the middle of the diagram, we have the global waypoint planning module. It takes the data site locations, values and power budget as input, denoted by config. Then it determines the preferences of different zones or data sites and passes that as input to the waypoint computation routine, which gives the next waypoint to be visited.

Next, we have the obstacle avoidance module on top. It takes image data, identifies obstacles, processes that into a obstacle-free terrain map, and computes path between consecutive waypoints. It also takes the GPS coordinates as input to localize the drone for identifying the movement direction.

Finally, if the priorities of the data sites change, the updated path is computed incrementally, instead of running the waypoint planning module all over again to save power. Hence, we have this incremental path recomputation module at the bottom, that takes the updated preferences and the current position from gps as input and calculates the changes in the pre-planned path.

7 of 15

Global waypoint planning

Often modeled as “prize collecting traveling salesman problem” (PCTSP)
Node contain the data site locations and values (prizes)
Edges denote the power requirement for travelling between two nodes
The goal is to maximize the total prize collected
NP-hard, so we need an approximate solution to act promptly trading off accuracy

We propose a fast greedy heuristic: Ellipse-greedy algorithm

Fix start and end points according to the power budget (S0, E0)
Build paths incrementally

Iteratively search for the site with the highest value that fits in power constraints (S1). The reachable sites form an elliptical area (region 0).
Use the new site to assign power quota and run the algorithm recursively on new pairs of points (S0, S1), (S1, E0).

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

8 of 15

Obstacle avoidance

Computes collision free sub-trajectories between the waypoints with observations of the surroundings (images from camera)

Semantic Segmentation

Weighted Rapidly-exploring Random Tree (RRT) Pathfinding

Drone Moving

Image

Helps navigate in complex spaces with obstacles
Incrementally constructs paths with space-filling tree
Tree node selection is biased towards open, safe areas with semantic segmentation results

Identifies obstacles from the images of surroundings
DNN model: EfficientNet-UNet (lightweight + efficient)

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

9 of 15

Incremental path recomputation

Some data-sites on the planned path need to be avoided for safety
Adjusting path can help maximize the cumulative value of the data sites to be visited

No, because of triangle property: QE + EF > QF

Change path to ABPQEF if it fits in power budget

Otherwise, say, site B has a lower value than site E. Then change path to APQEF if it fits in power budget (otherwise, change to ABPQF)

If APQEF satisfies the power budget, do we need to check APQF?

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

The last module, incremental path recomputation, comes into play when there is a need to change the pre-planned path. This is mainly for two reasons.

First, there could be some data sites on the planned path that needs to be avoided for safety reasons.�Or, there could be data sites whose priority got updated and so it is beneficial to visit more valuable data-sites. Let’s look into the first scenario.

Suppose, a drone has its initially planned path ABCDEF.�Now during its flight, if it is notified that there is a danger zone PQRS lying ahead, it would want to avoid data sites in that zone.�If it can avoid only C and D and travel from B to P, P to Q and then Q to E, the loss in values because of skipping data sites is minimal. But it may not be able to do so for power budget.�So, in the computation we incrementally move back from B or move forward from E. Say, we check with the path, APQE and find that this path is feasible in terms of power budget. In that case, we skip paths that skip E, by making use of the triangle property in geometry that tells us, since QR+EF > QF, if APQEF is feasible, so is APQF.

10 of 15

Experimental Results

Simulation studies
Location: Manhattan, New York
Geospatial & visual data from OpenStreetMap, Google Maps API
Maximum cruising distance of drones: 5km, radius of visual observation: 50m

Task	Metrics	Methods compared
Global waypoint planning	i. Reward: the cumulative values of the data sites visited�ii. Runtime distribution	i. Ellipse greedy algorithm ii. A* search (baseline) iii. Simulated annealing (baseline)
Real-time obstacle avoidance	i. Response time ii. Safety in navigation	i. Weighted RRT ii. Naive RRT
Dynamic path recomputation	i. Runtime	i. Incremental recomputation ii. Full recomputation

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

11 of 15

Results - Global waypoint planning

X-axis: # of drones

Y-axis: Runtime of algorithms

Lower is better

Averages

Greedy: 124.84 s

A* : 256.65 s

SA : 814.33 s

Takeaway

Greedy runs ~ 2-6.5 times faster

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

12 of 15

Results - Global waypoint planning

X-axis: # of drones

Y-axis: Reward collected by algorithms

Higher is better

Averages

Greedy: 1914.80

A* : 1524.34

SA : 1683.74

Takeaway

i. Greedy collects more rewards

ii. It has less fluctuations

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

13 of 15

Results - Obstacle avoidance

X-axis: Response (convergence) time

Y-axis: % of runs that resulted in the convergence time specified on X-axis

Higher y (%) at lower x (time), and lower y at higher x are better

Takeaway

Weighted RRT converges faster

Responds in 1s for ~80% of the runs but naive RRT does that for only ~20%

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

14 of 15

Summary

D-planner: An efficient surrounding-aware system for drone swarm path planning for urban battlefield coverage�
Solution techniques

Layered architecture for three sub-problems: global waypoint planning, obstacle avoidance, and incremental path computation
Ellipse greedy: a greedy approximation algorithm for global waypoint planning
EfficientNet-UNet (lightweight vision model) + weighted RRT: obstacle avoidance coupled with semantic segmentation
Geometry aided optimization for incremental path calculation

Experimental strength

Ellipse greedy takes 2-6.5x less time than baselines collecting more/comparable rewards
Obstacle avoidance with weighted RRT converges in 1s in 4x more % of runs

Envisioned future works

Drone navigation in adversarial environment with mobile entities
In-flight drone swarm communication for better coverage

28 October–1 November 2024 // Washington, DC, USA // IEEE Military Communications Conference

1 of 15

2 of 15

3 of 15

4 of 15

5 of 15

6 of 15

7 of 15

8 of 15

9 of 15

10 of 15

11 of 15

12 of 15

13 of 15

14 of 15

15 of 15