Constrained Entropy Maximization for Unpredictable Planning

19 concepts11 papers1 proposal

In classical robotics and operations research, an "optimal" plan is typically one that minimizes a well-defined cost metric, such as path length, travel time, or energy consumption. However, when an autonomous agent operates in an adversarial or competitive environment, this traditional definition of optimality introduces a severe vulnerability: predictability.

If a security drone always takes the shortest path between two surveillance points, or if a military unit schedules patrols at perfectly regular intervals, an adversary can easily observe, model, and exploit these patterns. To counter strategic opponents, autonomous agents must intentionally sacrifice a degree of efficiency to achieve unpredictability.

The core insight of recent research in this domain is that unpredictability should not be injected as arbitrary noise. Instead, it can be mathematically optimized by framing strategy design as a problem of constrained entropy maximization. By maximizing the entropy of a trajectory or schedule subject to a baseline performance threshold, agents can minimize the information leaked to observers while ensuring their primary mission objectives are still successfully met.


The Vulnerability of Efficiency and the Curse of Correlation

To understand why constrained entropy maximization is necessary, we must first look at how strategic adversaries exploit patterns. In security games—such as scheduling patrols at airports or ports—defenders often randomize their schedules over a set of optimal routes. However, simply choosing a randomized strategy is insufficient if the chosen paths are highly correlated.

As identified by Haifeng Xu et al. in Mitigating the Curse of Correlation in Security Games by Entropy Maximization, defenders frequently suffer from the "Curse of Correlation." If a defender's randomized resource allocation creates predictable spatio-temporal patterns, an attacker can exploit these correlations through surveillance. For instance, if observing a patrol boat at Location A implies that Location B will be left unguarded for the next hour, the attacker gains actionable intelligence despite the defender's randomized deployment.

To neutralize this information leakage, Haifeng Xu et al. in Security Games with Information Leakage: Modeling and Computation proposed a maximum entropy sampling approach. Instead of choosing any valid randomized schedule, the system selects a probability distribution over pure strategies that maximizes Shannon entropy while satisfying the required marginal coverage probabilities for each target.

$$\max \quad H(X) = -\sum_{x} P(x) \log P(x)$$ $$\text{subject to} \quad \sum_{x \in \mathcal{X}_i} P(x) = c_i \quad \forall i$$

This optimization minimizes the correlation between different targets. By maximizing the entropy of the overall strategy, observing the status of one location reveals the least possible information about the status of others, making the system robust against surveillance.


The Mechanism of Constrained Randomization

How do we implement this unpredictability without compromising the agent's primary mission? Pure randomness (such as a uniform random walk) would cause a robot to wander aimlessly, failing to complete its tasks efficiently or running out of energy.

The solution lies in a threshold-constrained optimization framework. As explored by Rashi Aswani et al. in Improving Surveillance Using Cooperative Target Observation, there is an inherent tension between maximizing the time targets are under observation and maintaining enough movement entropy to remain unpredictable. Focusing exclusively on tracking efficiency results in rigid behaviors that strategic targets can easily bypass. By introducing controlled randomization, the observer maintains high coverage rates while maximizing path entropy to thwart strategic evasion.

This trade-off is operationalized by maximizing behavioral or trajectory entropy subject to a minimum expected reward or performance threshold. In Unpredictable Planning Under Partial Observability, Michael Hibbard et al. demonstrated that maximizing the entropy of an agent's trajectory is functionally equivalent to minimizing the information leaked to an external observer. Their framework maximizes the unpredictability of an agent's path while satisfying a minimum expected reward threshold, ensuring that an adversary gains the minimum possible predictive information about future states without compromising the agent's ability to complete its mission.

A real-world application of this principle is found in the PROTECT system deployed by the U.S. Coast Guard for patrolling ports. As detailed by Bo An et al. in PROTECT: An Application of Computational Game Theory for the Security of the Ports of the United States, the system accounts for bounded human rationality using a Quantal Response model and applies uniform randomization across all equivalent optimal schedules. Maximizing the entropy of the deployed strategy ensures that even if an adversary learns the overall probability distribution, the specific timing and sequence of patrols remain highly unpredictable.


Fine-Grained Unpredictability: Trajectory vs. Return Time Entropy

Depending on the operational context, "unpredictability" can be formalized through different mathematical formulations of entropy. Two primary paradigms have emerged: trajectory-based entropy and return-time-based entropy.

Trajectory and Smoother Entropy

When an agent wants to prevent an adversary from reconstructing its entire historical path or predicting its future destination, it optimizes for trajectory entropy. In Smoothing-Averse Control: Covertness and Privacy from Smoothers, Timothy L Molloy formulated control as an optimization problem where the objective is to maximize the uncertainty (entropy) of an adversary's estimate of the system's entire state trajectory.

While traditional privacy filters focus on hiding individual measurements or current states, smoothing-averse control protects the full path history against Bayesian smoothers. Prioritizing smoother entropy over direct goal-seeking naturally leads to more circuitous, complex, and unpredictable paths, making the robot's complete trajectory significantly harder for an adversary to track or intercept.

Return Time Entropy

In long-term robotic surveillance, an adversary is often not trying to track the robot's exact path, but is instead waiting for the robot to leave a specific target so they can launch an attack. If a robot patrols a series of nodes using a standard Markov chain, it might achieve optimal coverage speed, but the time intervals between its visits to a specific node might have low variance. An intruder can exploit this by timing their actions based on the robot's departure.

To counter this, Xiaoming Duan et al. introduced the concept of "return time entropy" in Markov Chains With Maximum Return Time Entropy for Robotic Surveillance. Instead of maximizing the basic entropy rate of the transition sequence, their approach maximizes the entropy of the return times to specific nodes.

As synthesized in their broader survey, Markov Chain-Based Stochastic Strategies for Robotic Surveillance, maximizing return time entropy explicitly increases the variance in the duration between consecutive visits. This enhanced unpredictability complicates an intruder's ability to anticipate the robot's presence. Simulations indicate that surveillance strategies designed to maximize return time entropy consistently outperform those focused solely on speed or basic transition entropy when facing rational, calculating intruders.


Generalization Across Physical and Cyber Domains

The mathematical framework of constrained entropy maximization extends beyond high-level path planning into physical kinematics and hardware security.

Kinematic and Physical Evasion

In physical tracking scenarios, agents must balance the physical costs of erratic movement against the security benefits of unpredictability. For instance, Hailong Huang et al. developed a decentralized Model Predictive Control (MPC) approach in Decentralized Covert and Collaborative Radio Surveillance on a Group of Mobile Ground Nodes by a UAV Swarm that optimizes UAV trajectories by maximizing a kinematic randomness objective subject to signal-to-noise ratio thresholds. This allows the UAVs to maintain sufficient signal reception for data extraction while avoiding predictable paths that would reveal their covert intentions.

At a fundamental level, this trade-off between energy consumption and maneuver unpredictability can be mapped to quantum mechanics. In Optimal Stochastic Evasive Maneuvers Using the Schrödinger’s Equation, Magnus Egerstedt et al. demonstrated that when a prey agent optimally balances its energy expenditure with the need to remain unpredictable to a predator, the resulting stochastic evasion strategy can be mathematically described by the stationary Schrödinger's equation.

Hardware Side-Channel Defense

The principle of maximizing an opponent's uncertainty also applies to digital and architectural security. Machine-learning-based side-channel attacks operate by analyzing hardware signals (such as power consumption or electromagnetic emissions) to predict secret states or cryptographic keys.

To counter this, Hyoungwook Nam et al. developed the FriendlyFoe architecture in FriendlyFoe: Adversarial Machine Learning as a Practical Architectural Defense against Side Channel Attacks. By using adversarial machine learning to inject intelligent, on-the-fly noise into hardware and software channels, the defense explicitly optimizes the system to maximize the entropy of an attacker's output. This neutralizes machine-learning-based side-channel attacks across unknown, black-box classifiers without needing to predict the specific architecture of the attack model, all while minimizing performance and power overheads.


Conclusion

Whether applied to a Coast Guard patrol boat, a surveillance drone, or a hardware processor, the core philosophy remains identical: predictability is a vulnerability that can be engineered away. By shifting from purely deterministic optimization to constrained entropy maximization, modern autonomous systems can guarantee a mathematically rigorous level of unpredictability, forcing adversaries to operate under maximum uncertainty while ensuring that primary mission objectives remain securely within reach.

Key Foundational Work

PROTECT: An Application of Computational Game Theory for the Security of the Ports of the United States (2012) — contributed 1 concept elements to this direction.
Security Games with Information Leakage: Modeling and Computation (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_return_time_entropy_2b7f1332,
  title = {return time entropy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/return-time-entropy/rdr_2b7f1332214646aa8966132a859415b4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_return_time_entropy_2b7f1332_v1,
  title = {return time entropy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/return-time-entropy/rdr_2b7f1332214646aa8966132a859415b4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake