Greedy Perspectives: Multi-Drone View Planning for Collaborative Perception in Cluttered Environments

K Suresh, Aditya Rauniyar, Micah Corah, Sebastian Scherer

TL;DR

This paper introduces a sequential greedy planning approach for teams of drones to film groups of moving actors in cluttered environments. By leveraging submodular maximization and an occlusion-aware objective, the system enables multiple robots to coordinate complex viewing behaviors—like splitting up to follow diverging groups—while outperforming traditional formation-based planning by up to 14%.

What Problem Does This Paper Address?

Filming a single person with a drone is a solved problem for many consumer products. However, filming a group of people (actors) with a team of drones in a complex environment (like a forest or a city) is significantly harder.

The challenges are three-fold:

  1. Combinatorial Complexity: The joint state space of multiple robots and multiple actors grows exponentially, making optimal planning intractable.
  2. Environmental Obstacles: Trees and buildings cause occlusions (blocking the view) and pose collision risks.
  3. Dynamic Group Behavior: Actors may split, merge, or spread out, requiring the drone team to reconfigure their "formation" on the fly.

Existing methods often rely on rigid formations or focus on a single actor. This paper seeks a more flexible approach that allows drones to collaborate to maximize the "quality" of the collective footage.

Methods

The authors frame the problem as submodular maximization. In simple terms, they define a "view reward" that exhibits diminishing returns: the first drone to see an actor's face provides a huge reward, but the fifth drone seeing the same face from the same angle adds very little.

Key components include:

  • Sequential Greedy Planning: Instead of planning for all drones at once, the drones plan one by one. Each drone chooses the best path for itself, taking into account the planned paths of the drones that came before it.
  • Occlusion-Aware Objective: To calculate rewards, the system uses an OpenGL-based renderer to simulate what each drone sees. It counts "pixels" on the actors' surfaces, adjusted by a square-root function to encourage drones to cover different actors and different angles.
  • MDP Formulation: Each single-robot planning problem is modeled as a Markov Decision Process (MDP) on a Directed Acyclic Graph (DAG). This allows the robot to find its optimal path efficiently using value iteration.
  • Collision Constraints: The planner prunes any actions that would result in a collision with the environment or other drones.

Datasets

The approach was evaluated in five custom-designed simulated environments, each testing a specific coordination challenge:

  • Split: Two actors move together and then split around an obstacle.
  • Large: A scaling test with 18 robots and 6 actors.
  • Merge: Actors move around a corner in opposite directions, requiring drones to "hand off" targets.
  • Corridor: A highly constrained narrow space.
  • Forest: A dense environment with many obstacles and occlusions.

The mesh for the environments was based on a real-world dataset of the CMU campus.

Key Insights and Ideas

  • The "Collision Guarantee" Paradox: Mathematically, adding inter-robot collision constraints violates the formal "near-optimality" guarantees of submodular greedy planning. However, the authors found that in practice, the performance loss is negligible. Drones are smart enough to find high-reward paths that don't involve crashing into each other.
  • Emergent Behavior: The system wasn't told to "split the team" or "hand off an actor." These behaviors emerged naturally from the optimization of the view reward. For example, in the Split scenario, the drones automatically divided themselves to follow both groups.
  • Efficiency through Caching: While the theoretical complexity is quadratic relative to the number of robots, the authors achieved near-linear scaling in computation time by caching camera model evaluations, as robots often share the same sensor characteristics.

Key Results

  • Superior Coverage: The sequential planner generated 14% greater view reward than a standard formation-based planner in the Merge, Corridor, and Forest scenarios.
  • Robustness: In the Forest scenario, the sequential planner (using only 2 robots) outperformed a formation planner that was given 3 robots "for free," proving that smart positioning beats raw numbers.
  • Collision Avoidance: The "Sequential" (collision-aware) and "Seq. w/o Inter-Robot" (collision-ignorant) planners achieved nearly identical rewards, suggesting that the robots can avoid each other without compromising the mission objective.

Limitations and Future Work

The current system operates under several "strict" assumptions: it requires a known map, known (or perfectly predicted) actor trajectories, and a known starting state for the robots.

To move this to real-world, "unscripted" environments, the authors suggest:

  • Receding-Horizon Planning: Moving from offline planning to a real-time "rolling" window to handle uncertainty.
  • Perception-in-the-loop: Integrating real-time tracking (like Kalman filters) to estimate actor positions.
  • Task Expansion: Extending the framework beyond simple filming to more complex tasks like 3D human pose reconstruction, where specific viewpoints are required for mathematical accuracy.

Summary updated

Abstract

Deployment of teams of aerial robots could enable large-scale filming of dynamic groups of people (actors) in complex environments for applications in areas such as team sports and cinematography. Toward this end, methods for submodular maximization via sequential greedy planning can enable scalable optimization of camera views across teams of robots but face challenges with efficient coordination in cluttered environments. Obstacles can produce occlusions and increase chances of inter-robot collision which can violate requirements for near-optimality guarantees. To coordinate teams of aerial robots in filming groups of people in dense environments, a more general view-planning approach is required. We explore how collision and occlusion impact performance in filming applications through the development of a multi-robot multi-actor view planner with an occlusion-aware objective for filming groups of people and compare with a formation planner and a greedy planner that ignores inter-robot collisions. We evaluate our approach based on five test environments and complex multi-actor behaviors. Compared with a formation planner, our sequential planner generates 14% greater view reward for filming the actors in three scenarios and comparable performance to formation planning on two others. We also observe near identical view rewards for sequential planning both with and without inter-robot collision constraints which indicates that robots are able to avoid collisions without impairing performance in the perception task. Overall, we demonstrate effective coordination of teams of aerial robots in environments cluttered with obstacles that may cause collisions or occlusions and for filming groups that may split, merge, or spread apart.
BibTeX
@misc{suresh2023greedy,
  author = {K Suresh and Aditya Rauniyar and Micah Corah and Sebastian Scherer},
  title = {{Greedy Perspectives: Multi-Drone View Planning for Collaborative Perception in Cluttered Environments}},
  year = {2023},
  eprint = {2310.10863},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.10863},
}

Loading related content...

Figure