⚡ electrical engineering

Trajectories for the Optimal Collection of Information

This paper proposes a hybrid computational approach that decomposes the high-dimensional state space of an aircraft's optimal sensor trajectory problem into a grid-based subspace for handling non-linearities and an ODE-based subspace for efficiency, thereby overcoming the intractability of traditional methods for minimizing estimation error via the Fisher Information Matrix.

Original authors: Matthew R. Kirchner, David Grimsman, Joao P. Hespanha, Jason R. Marden

Published 2026-08-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matthew R. Kirchner, David Grimsman, Joao P. Hespanha, Jason R. Marden

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a pilot flying an aircraft over a vast, featureless ocean, tasked with finding a single ship whose location is unknown. The pilot cannot see the ship directly. Instead, the aircraft is equipped with sensors that listen for faint signals—perhaps a radio transmission or a shift in sound waves caused by the ship's motion. Every time the aircraft flies past a new point, it gathers a tiny piece of information. The challenge is not just to collect data, but to collect the right data. If the plane flies in a straight line, the information gathered might be redundant, leaving the ship's location vague. But if the pilot steers the aircraft along a specific, winding path, the angles and timing of the measurements change, allowing the computer to pinpoint the ship's position with far greater accuracy. This is the core of a problem known as optimal information collection: how to move a sensor so that it learns the most about a hidden target in the shortest time.

For decades, mathematicians have known that the best way to solve this kind of movement problem is to treat it as a search for a perfect path through a landscape of possibilities. They use a powerful mathematical tool called the Hamilton-Jacobi equation, which acts like a map showing the best direction to go at every single point. However, this map becomes impossibly complex when the problem involves many variables. In the case of tracking a ship, the "map" must account for the plane's position, its speed, its heading, and the growing uncertainty about the ship's location. As the number of variables grows, the size of this map explodes, becoming so large that even the world's fastest supercomputers cannot calculate the answer in a reasonable time. This is a famous hurdle in science known as the "curse of dimensionality," where adding just a few more details to a problem makes it exponentially harder to solve.

In a recent study, researchers Matthew Kirchner, David Grimsman, João Hespanha, and Jason Marden tackled this specific bottleneck. They focused on a scenario where an aircraft with multiple sensors tries to track a moving target using a metric called the Fisher Information Matrix. Think of this matrix as a scorecard that measures how much a specific flight path reduces the uncertainty about the target's location. The goal is to find the flight path that maximizes this score, effectively shrinking the "error zone" around the target as much as possible. The researchers found that while the standard way of solving this problem—building a massive grid to cover every possible state—fails because the grid becomes too huge to manage, there is a clever way around it.

The team developed a new hybrid approach that splits the problem into two parts. They realized that the aircraft's physical movement (its position and heading) happens in a small, manageable space that can still be mapped with a grid. However, the "information" part of the problem, which tracks the accumulating data about the target, exists in a much larger, abstract space. Instead of trying to grid this massive information space, the researchers treated it differently. They kept the grid for the physical movement but used a set of simpler, continuous equations to calculate the information part on the fly. This is similar to how one might navigate a city by looking at a detailed street map for the immediate neighborhood while using a general compass direction for the long journey ahead, rather than trying to draw a map of the entire continent.

By combining a traditional grid for the physical motion with a streamlined calculation for the information gathering, the researchers were able to generate optimal flight paths that were previously impossible to compute. In their simulations, they tested this method with a model of an aircraft flying 1,000 meters above the ground, using sensors that detect Doppler shifts—the change in frequency of a signal as the source moves relative to the receiver. The target was a vehicle with an unknown location, initially believed to be somewhere within a circle with a standard deviation of 10 meters. The aircraft was limited to a maximum turn rate of 0.05 radians per second.

The results showed that the optimal path is not a simple straight line. Starting from a position 50 meters east and 36.6 meters south of the target's estimated center, the aircraft first performs a series of turning maneuvers. These turns are crucial because they allow the sensors to view the target from multiple angles, which is necessary to fully localize it using only Doppler data. Once the aircraft has gathered enough directional variety, it flies straight along a ray extending outward from the center of the estimated location. This specific shape—turning first, then flying straight—emerged consistently across many different starting positions, suggesting it is a robust strategy for this type of sensing problem.

The study confirms that this hybrid method works effectively for systems where the physical movement is simple but the information state is complex. The researchers demonstrated that by avoiding a full grid for the information dimension, they could solve problems that would otherwise be intractable. While the work was conducted through computer simulations rather than physical flight tests, the mathematical framework provides a rigorous way to generate these paths. The authors note that while they focused on a specific measure of information gain, the method could potentially be adapted for other types of sensors and metrics in the future. This approach offers a practical bridge between the heavy theory of optimal control and the real-world need to guide vehicles that must learn about their environment while they move.

Technical Summary: Trajectories for the Optimal Collection of Information

Problem Formulation
The paper addresses the problem of optimizing the flight trajectory of an aircraft equipped with heterogeneous sensors to maximize information gain regarding the location of a target vehicle with an unknown position ( $\theta$ ). The aircraft, modeled as a Dubins car with bounded turn rates, collects measurements (e.g., Doppler shifts, infrared, or RF data) along its path. The objective is to minimize the estimation error of the target's location.

The authors select the Fisher Information Matrix (FIM) as the metric for information quality. Specifically, they optimize the LOGDET metric (the negative log-determinant of the cumulative FIM), which corresponds to a D-optimal estimate and minimizes the volume of the error ellipsoid. This problem is formulated as an optimal control problem where the cost functional depends on the cumulative FIM, which in turn depends on the trajectory.

Methodological Challenges
The optimal value function for this problem satisfies a Hamilton-Jacobi (HJ) partial differential equation (PDE). While grid-based methods (Method of Lines, or MOL) are robust for handling the non-linear and non-convex structures inherent in FIM-based optimization, they suffer from the "curse of dimensionality." In this specific problem, the state space includes the vehicle's physical state ( $x \in \mathbb{R}^2 \times SO(2)$ ) and an augmented state ( $z$ ) representing the cumulative FIM. Since the dimension of $z$ scales with the square of the number of parameters to be estimated, a standard grid-based approach over the full state space becomes computationally intractable.

Proposed Methodology: Hybrid Method of Lines
To bridge the gap between rigorous HJ theory and practical implementation, the authors propose a hybrid Method of Lines (MOL) approach that decomposes the state space $\chi = (x, z)$ :

Decomposition: The system is treated as a cascade where the control input $u$ directly affects the physical state $x$ , while the augmented state $z$ evolves as an integral of a function of $x$ ( $\dot{z} = \ell(x)$ ).
Grid-Based Subspace ( $x$ ): A spatial grid is maintained only for the lower-dimensional physical state $x$ . Finite difference schemes (specifically Lax-Friedrichs approximations) are used to compute the gradient of the value function with respect to $x$ ( $V_x$ ). This preserves the robustness of grid methods against non-convexities in the physical domain.
ODE-Based Subspace ( $z$ ): The authors derive a theoretical result (Theorem 1) showing that the gradient of the value function with respect to the augmented state $z$ ( $V_z$ ) can be computed by solving a system of ordinary differential equations (ODEs) rather than using a spatial grid. This avoids the exponential scaling associated with the dimension of $z$ .
Hybrid Algorithm: The resulting algorithm solves a coupled system of ODEs at each grid point of $x$ . It simultaneously evolves the value function approximation $\phi$ and its gradient with respect to $z$ ( $\Phi$ ), utilizing the analytical relationship derived from the HJ equation's structure.

Key Contributions

Hybrid MOL Formulation: The paper introduces a novel decomposition strategy for HJ PDEs in cascade systems, allowing for the avoidance of spatial grids in high-dimensional subspaces while retaining them where necessary for non-linear stability.
Theoretical Derivation: The authors provide a rigorous derivation (Theorem 1 and Lemma 2) demonstrating that the gradient with respect to the integral state ( $z$ ) satisfies a specific ODE, enabling the grid-free treatment of the FIM accumulation.
Application to Sensor Placement: The method is specialized for the optimal information collection problem, providing a computationally feasible way to generate optimal trajectories for target tracking using the LOGDET metric.

Results
The authors present simulation results for a scenario involving a passive RF sensor measuring Doppler frequency shifts to track a target with a Gaussian prior distribution.

Trajectory Characteristics: The optimal trajectories generated by the hybrid method exhibit a distinct qualitative behavior. Starting from various initial conditions, the aircraft performs initial turning maneuvers to gather measurements from multiple directions. Following this, the aircraft travels along a straight ray extending outward from the center of the prior distribution.
Rationale: The initial maneuvers are necessary to resolve the target's position in multiple dimensions (since Doppler measurements alone are ambiguous without angular diversity), while the subsequent straight path maximizes the variation in Doppler shift relative to the target, thereby maximizing information gain.
Robustness: The simulations demonstrate that the method successfully generates optimal paths for different initial vehicle positions, maintaining the qualitative properties of the solution despite variations in initial conditions.

Significance and Claims
The paper claims that this hybrid approach effectively addresses the "curse of dimensionality" that typically renders HJ-based optimal control intractable for sensor placement problems with high-dimensional information states. By leveraging the specific cascade structure of the problem, the method achieves a balance between the robustness of grid-based methods (handling non-convexities in the physical state) and the efficiency of ODE-based methods (avoiding grids in the information state).

The authors note that while the current work focuses on the LOGDET metric, the framework is applicable to other metrics provided they meet certain conditions. They explicitly state that analysis of other metrics, such as the trace of the inverse (A-optimal), is outside the scope of this paper and reserved for future work. The paper concludes by suggesting that future research will investigate generalizing this hybrid MOL approach to broader classes of cascade systems.

More like this