In most path-planning problems, the objective is simple: find the shortest or most efficient route from point A to point B. However, in adversarial environments—ranging from military operations to competitive video games—efficiency can be a liability. If an observer can predict an agent's destination early in its trajectory, they can intervene, intercept, or prepare a defense.
To counter this, researchers have developed Deceptive Path-Planning (DPP). The goal is to reach a destination while strategically manipulating an observer's beliefs to keep the true objective hidden for as long as possible.
The Geometry of Ambiguity
The most intuitive way to hide a goal is to remain non-committal. If an agent moves directly toward a target, it immediately signals its intent. To prevent this, Pozanco et al. propose the use of Centroids and Minimum Covering States.
Instead of moving toward a specific goal, the agent moves toward a state that is strategically positioned relative to multiple potential goals. By staying equidistant from several targets, the agent delays commitment. This "strategic ambiguity" ensures that even a rational observer cannot distinguish which target is the true one until the agent is forced to make a final break toward the destination.
Deception as Information Control
Deception is essentially the management of information flow. Strouse et al. frame this using information theory, training agents to be "poker-faced." By minimizing the mutual information between their actions and their goals, agents learn to adopt trajectories that reveal nothing about their ultimate intent.
This can be formalized through a Bayesian lens. As Sreedharan et al. explain, an observer typically maintains a probability distribution (a posterior) over the agent's possible goals. A deceptive agent seeks to maximize the entropy of this distribution. If the observer’s belief is spread thinly across many possibilities, the agent has successfully obfuscated its intent. Xu and Yin further this by treating "relative goal uncertainty" as a controllable metric, allowing agents to actively "dial up" the confusion they cause.
The Cost of Being Suboptimal
True deception often requires a departure from perfect efficiency. To mislead an observer, an agent might take a longer path or move in a direction that seems irrational. Lourenço et al. describe this as belief obfuscation. By intentionally selecting suboptimal actions, the agent creates a discrepancy that prevents the observer from using "inverse optimization" to reconstruct the agent's private goals.
However, there is a fundamental trade-off between deception and cost. A path that is 100% deceptive but never reaches the goal is useless. Masters et al. introduced the "path completion" metric to balance these competing needs, ensuring agents remain "rationally deceptive." Modern approaches, such as those by Chen et al., use reinforcement learning to find these optimal balances under strict time constraints, ensuring the agent doesn't spend so much time deceiving that it fails its mission.
Active Deception and Decoys
Beyond mere ambiguity, agents can engage in active misinformation. Luo et al. suggest using decoy goals and diverse routes to actively lead an observer to the wrong conclusion. This shifts the strategy from "I don't want you to know where I'm going" to "I want you to think I'm going somewhere else."
This becomes particularly powerful when the observer can intervene. Suttle et al. demonstrate that by strategically revealing just enough information, an agent can trick an observer into making "suboptimal interventions." In this sense, the agent isn't just hiding; it is baiting the adversary into wasting resources on the wrong target.
Scaling the Illusion
While the math of deception is elegant, it is computationally expensive. Calculating the observer's likely beliefs at every step of a path is a "brutal" task, as noted by Ott et al.. To make these strategies practical for real-world robotics or large-scale simulations, Hu et al. utilize hierarchical subgoal graphs. By abstracting the map into high-level nodes, agents can plan deceptive routes across large environments without the exponential processing overhead of traditional methods.
Through these mechanisms—geometric ambiguity, information regularization, and strategic suboptimality—deceptive path planning transforms navigation from a simple search problem into a sophisticated game of mental models.
Key Foundational Work
Deceptive Path-Planning (2017) — contributed 3 concept elements to this direction.
Feedback Navigation in an Uncertain Flowfield and Connections with Pursuit Strategies (2012) — contributed 1 concept elements to this direction.