1 of 15

Multi-Agent Planning for Search

Seungchan Kim, Sagar Sachdev, Troy Vicsik

2 of 15

Motivation

Perform multi-agent planning for search operations at sea

Informative-path planning for 2 UAVs for search operations

Need to avoid collisions between UAVs

Seeking high information gain while subject to budget constraints (battery life, time limits, etc.)

Achieved by taking in the belief space from one plan and inputting it into the other

3 of 15

Planning Representation

States:

Start State: [x_i, y_i, z_i, psi_i]
Multiple goal states (every ship it flies over is a goal state)
Planning ends when budget finishes

World: Discretized 3-dimensional grid

P(X) = Probability of containing relevant data

Information reward function: Reduction in Entropy

Synonymous with maximizing information gain
Potential information gain tracked along path edges
Shannon Entropy: H(X) = −P(X) log P(X) − P(¬X) log P(¬X)

Output Goals: To achieve the goal state with maximum reward (aka maximum reduction in the entropy) and (if time permits), without covering the same area

In other words, minimize overlap in information detected by two drones

Moon, B., Chatterjee, S., & Scherer, S. (2022). TIGRIS: An Informed Sampling-based Algorithm for Informative Path Planning. Arxiv. https://doi.org/{10.48550/ARXIV.2203.12830}

4 of 15

Search Algorithm

Planner: TIGRIS – An Informed Sampling Based Algorithm for Informative Planning

Path Solver: Trochoidal path solver - Provides an analytical solution for Left-Straight-Left and Right-Straight-Right trajectories and a numerical solution for all other cases

Techy, L., & Woolsey, C. A. (2009). Minimum-Time Path Planning for Unmanned Aerial Vehicles in Steady Uniform Winds. Journal of Guidance, Control, and Dynamics, 32(6). https://doi.org/https://doi.org/10.2514/1.44580

Why use trochoids?

Easy to implement, computationally inexpensive to implement and cheaper than dubins computations. Extremal paths comprise of straight segments and the arcs constitute trochoidal segments The path-planning problem therefore reduces to identifying the switching points at which straight and trochoidal path segments join to form a feasible path and choosing the true minimum-time solution from the resulting set of candidate extremals.

TIGRIS: Tree-based Information Gathering using Informed Sampling

TIGRIS does well at quickly finding paths that maximize the information reward and reducing entropy over the belief space. As the budget increases to be large relative to the search space, the performance of TIGRIS would be expected to degrade as the problem approaches that of a coverage planner and the density of the tree would need to be intractably high. In these situations, replanning on the fly with TIGRIS could be a potential solution and is slated for future work.

5 of 15

Results

Figure 1: Plan output after providing a region of interest as a line-segment target prior

6 of 15

Results

Figure 2: Results showing plans for two polygons (regions with possible ships)

Figure 3: Results showing plans for four polygons (regions with possible ships)

7 of 15

Quantifiable Results

Results from TIGRIS Planner and Trochoidal Solver (averaged over 5 runs)
Priors	Time (s)	Reward Gained	Budget Used (distance traveled; of 6000)	# of Samples	# of Waypoints in Path
Line Segments	60	73.39	5907.68	229	37
2 Polygons (Ships)	60	86.39	5900.17	116	43
4 Polygons (Ships)	60	148.69	5900.67	130	38

8 of 15

Video of Preliminary Trials

Results prior to tuning with line segment priors

9 of 15

Improved Results with Parameters Tuned

Results after tuning with line-segment priors

10 of 15

Results on 2 ships and 4 ships

Tuned plans with polygon priors simulating two regions of interest (ships) with wind

Tuned plans with polygon priors simulating four regions of interest (ships) without wind

11 of 15

References

Moon, B., Chatterjee, S., & Scherer, S. (2022). TIGRIS: An Informed Sampling-based Algorithm for Informative Path Planning. Arxiv. https://doi.org/{10.48550/ARXIV.2203.12830}
Singh, A., Krause, A., Guestrin, C., & Kaiser, W. J. (2009). Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research, 34, 707–755. https://doi.org/10.1613/jair.2674
Techy, L., & Woolsey, C. A. (2009). Minimum-Time Path Planning for Unmanned Aerial Vehicles in Steady Uniform Winds. Journal of Guidance, Control, and Dynamics, 32(6). https://doi.org/https://doi.org/10.2514/1.44580

12 of 15

Acknowledgements

The team would like to thank Brady Moon and Dr. Sebastian Scherer for their guidance with this project.

13 of 15

Software infrastructure and deliverables

Visualization Tools : RViz within ROS
Minimum Deliverable: To discretize the search area and run TIGRIS + Trochoids on a single UAV, quantify plan quality, plan length and entropy
Maximum Deliverable: Intelligent coverage of area for multiple (2) UAVs - Avoid planning over the same area to maximize area coverage, and compute maximum reward

14 of 15

Multi-drone Planning Roadmap

Test out TIGRIS + Trochoids plan for a single UAV and have a baseline simulation running
Integrate TIGRIS + Trochoids for 2 UAVs and have them running in the same RViz simulation independently of each other

Add separate topic-names for different planners
Identify planning parameters of interest
Identify how to share the belief space

Work on intelligent area coverage - Develop a planning strategy such that the same area is not covered by both the drones/fixed wings
Metrics to evaluate: Plan Quality and Entropy

15 of 15

References

Techy, L., & Woolsey, C. A. (2009). Minimum-Time Path Planning for Unmanned Aerial Vehicles in Steady Uniform Winds. Journal of Guidance, Control, and Dynamics, 32(6). https://doi.org/https://doi.org/10.2514/1.44580