Probabilistic Plan Legibility with Off-the-shelf Planners

Michele Persiani; Thomas Hellström

cs.ROSep 4, 2026

Probabilistic Plan Legibility with Off-the-shelf Planners

Authors: Michele Persiani, Thomas Hellström

Organizations: Umeå University, Umeå, Sweden

Abstract

Legible planning is the creation of plans that best disambiguate their goals from a set of other candidates from an observer's perspective. In this paper we propose a method for legible planning for arbitrary PDDL domains, by extending previous research on legibility to classical planning without requiring to construct ad-hoc planners. We also discuss how the observer perspective may be estimated through a second order theory of mind that connects the planner's and the observer's task spaces. Our solution can for example be deployed in human-robot teaming scenarios, where an autonomous robot in a team can implicitly communicate its goal by producing legible plans. We present benchmark results on several PDDL planning domains. Our results generally show that plan legibility is a trade-off with plan efficiency, however, not all planning domains allows to increase legibility in the same way and a regularizing factor to balance legibility and efficiency was proved necessary.

Figures & tables

Figure 1: Legible planning requires a second order theory of mind, by which the planner, working e.g. on a mobile robot $R$ , estimates how the observer $O$ interprets the robot’s actions by using a first order theory of mind of the robot. Legibility of plans is computed inside $\Xi_{pl}^{\prime}$ that is $O$ ’s model of $R$ .

Figure 2: Legible planning in the rescue scenario. Left side: world grid that the commander believes the robot is planning for. This plan instance is estimated internally by the robot through a theory of mind, and doesn’t have any obstacles. Right side: real world grid computed by the robot, which has the real goal and contains detected obstacles.

Domain	$\|\mathcal{A}\|$	$\|\mathcal{P}\|$	$\|I\|$	$\|G\|$	$\|\overline{\pi}\|$
intrusion	9.0	11.0	1.0	4.75	17.15
kitchen	29.0	23.0	2.0	1.0	10.6
satellite	5.0	12.0	62.8	6.8	16.55
campus	22.0	12.0	1.0	2.75	4.925
blocks-world	4.0	5.0	14.4	4.95	15.25
logistics	6.0	3.0	22.7	2.3	31.25

Table 1: Average instance measures over the tested planning domains. The columns, from left to right are: number of operators, number of predicates, size of the initial state, size of the goal, length of optimal plan.

		$\gamma$
		$0$		$0.001$		$0.01$		$0.1$
$d\%$	domain	$\mathcal{L}_{gain}$	$\mathcal{C}_{gain}$	$\mathcal{L}_{gain}$	$\mathcal{C}_{gain}$	$\mathcal{L}_{gain}$	$\mathcal{C}_{gain}$	$\mathcal{L}_{gain}$	$\mathcal{C}_{gain}$
0	campus	$1.32$	$1.1$	$1.31$	$1.1$	$1.26$	$1.1$	$1.08$	$1.03$
	kitchen	$1.43$	$1.26$	$1.37$	$1.26$	$1.16$	$1.11$	$1.0$	$1.0$
	satellite	$1.38$	$1.34$	$1.35$	$1.32$	$1.2$	$1.2$	$1.01$	$1.01$
	intrusion	$1.0$	$1.0$	$1.0$	$1.0$	$1.0$	$1.0$	$1.0$	$1.0$

Table 2: Computed plan legibility and cost measures.

\mathcal{L}_{gain}

: cost gain,

\mathcal{C}_{gain}

: legibility gain,

d\%

: percentage of dropped observations,

\gamma

: regularization factor towards cheap plans. Values are for

k=200

Panel of Figure 3 — Figure 3: Legibility gain for various percentages of dropped parameters.

	$k$	50	100	200
$\gamma=0$	$\mathcal{L}_{gain}$	1.31	1.43	1.54
$\gamma=0$	$\mathcal{C}_{gain}$	1.36	1.47	2.09
$\gamma=0.01$	$\mathcal{L}_{gain}$	1.13	1.18	1.16
$\gamma=0.01$	$\mathcal{C}_{gain}$	1.18	1.21	1.36
$\gamma=0.1$	$\mathcal{L}_{gain}$	1.01	1.02	1.01
$\gamma=0.1$	$\mathcal{C}_{gain}$	1	1	1

Table 3: Average over all of the domains of legibility and cost gains for increasing values of

k

Symbolic Planning

Symbolic planning represents goals, states, and actions explicitly, then searches for action sequences that satisfy constraints.

See all 89 papers

From Legible to Inscrutable Trajectories: (Il)legible Motion Planning Accounting for Multiple Observers
Feb 9, 2026Ananya Yammanuru, Maria Lusardi, Nancy M. Amato +1Trajectory Optimization Trajectory Generation
University of Illinois at Urbana-Champaign, Urbana IL 61801, USA
LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs
Oct 6, 2026André G. Pereira, Augusto B. Corrêa, Felipe Meneguzzi +1Automated Heuristic Design LLM Planning
Federal University of Rio Grande do Sul Brazil · University of Oxford United Kingdom · University of Aberdeen United Kingdom +1
Agentic LLM Planning via Step-Wise PDDL Simulation: An Empirical Characterisation
Mar 6, 2026Kai Göbel, Pierrick Lorang, Patrik Zips +1LLM Planning LLM Agent Planning
AIT Austrian Institute of Technology GmbH, Vienna, Austria

Feb 9, 2026J/K move · Enter open · S save

From Legible to Inscrutable Trajectories: (Il)legible Motion Planning Accounting for Multiple Observers

Ananya Yammanuru, Maria Lusardi, Nancy M. Amato, Katherine Driggs-Campbell

University of Illinois at Urbana-Champaign, Urbana IL 61801, USA

Trajectory Optimization Trajectory Generation Motion Planning Robot Motion Planning

Open paper AskPDF arXiv

In cooperative environments, such as in factories or assistive scenarios, it is important for a robot to communicate its intentions to observers, who could be either other humans or robots. A legible trajectory allows an observer to quickly and accurately predict an agent's intention. In adversarial environments, such as in military operations or games, it is important for a robot to not communicate its intentions to observers. An illegible trajectory leads an observer to incorrectly predict the agent's intention or delays when an observer is able to make a correct prediction about the agent's intention. However, in some environments there are multiple observers, each of whom may be able to see only part of the environment, and each of whom may have different motives. In this work, we introduce the Mixed-Motive Limited-Observability Legible Motion Planning (MMLO-LMP) problem, which requires a motion planner to generate a trajectory that is legible to observers with positive motives and illegible to observers with negative motives while also considering the visibility limitations of each observer. We highlight multiple strategies an agent can take while still achieving the problem objective. We also present DUBIOUS, a trajectory optimizer that solves MMLO-LMP. Our results show that DUBIOUS can generate trajectories that balance legibility with the motives and limited visibility regions of the observers. Future work includes many variations of MMLO-LMP, including moving observers and observer teaming.

Abstract

Symbolic Planning

Explore similar work

From Legible to Inscrutable Trajectories: (Il)legible Motion Planning Accounting for Multiple Observers

LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs

Agentic LLM Planning via Step-Wise PDDL Simulation: An Empirical Characterisation