Classical planning aims to find a sequence of actions, a plan, that maps a starting state into one of the goal states. If a trajectory appears to be leading to the goal, should we prioritise exploring it? Seminal work in goal recognition (GR) has defined GR in terms of a classical planning problem, adopting classical solvers and heuristics to recognise plans. We come full circle, and study the adoption and properties of GR-derived heuristics for seeking solutions to classical planning problems. We propose a new divergence-based framework for assessing goal intention, which informs a new class of efficiently-computable heuristics. As a proof of concept, we derive two such heuristics, and show that they can already yield improvements for top-scoring classical planners. Our work provides foundational knowledge for understanding and deriving probabilistic intention-based heuristics for planning.
Figures & tables
f5
f5 -ol rrp
f5
f5 -op rrp
f5 -ol rrp
f5 -op rrp
Coverage (1831)
1,510
1,560 (5.03)
1,510
1,556 (1.5)
1,560 (5.03)
1,556 (1.5)
% Score
76.77%
80.20% (0.35)
76.77%
79.90% (0.15)
80.20% (0.35)
79.90% (0.15)
N Fewer Expansions
368.2 (6.7)
1,134.4 (8.7)
341.4 (9.1)
1,159.4 (8.0)
412.0 (7.3)
716.6 (6.5)
N Lower Time
582.4 (99.5)
897.0 (92.2)
658.8 (117.3)
814.6 (102.4)
811.8 (130.1)
658.0 (122.6)
N Lower Plan Cost
760.6 (8.9)
369.6 (7.6)
763.6 (2.9)
375.8 (1.7)
375.2 (4.5)
349.2 (13.4)
Average EpS
40,111
35,680
40,111
33,626
35,680
33,626
Table 1: Enhancing a basic BFWS( f5 ) solver with proposed ol rrp and op rrp heuristics. % score is the average of the % of instances solved in each problem domain. Results for comparisons and solvers with a randomised component represent the mean, and include the standard deviation across 5 measurements. N Fewer Expansions, N Lower Time and N Lower Plan Cost represent the number of problems where a variant scores better in the respective metrics (ignoring ties). Avg. EpS represents the average number of expansions per second across problems solved by all planners, and proxies computational overhead. Results indicate that ol rrp and op rrp reduce the number of expansions across a significant portion of problems, on average improving also coverage and solution time. Such improvements come at the cost of on average worse plan quality compared to the baseline.
Planner
Coverage (1831)
% score
Agile score
Dual-BFWS
1,607
83.6%
1,200.8
ApxNoveltyT
1,611 (3.5)
83.8% (0.2)
1,233.7 (0.2)
LAMA
1,535
79.1%
1,192.3
Scorpion-M
1,591
82.9%
1,206.4
OL rrp
1,621 (3.2)
84.6% (0.3)
1,229.4 (3.4)
OL rrp -UTP
1,616 (2.1)
84.2% (0.1)
1,236.0 (1.9)
Table 2: Mean coverage and Agile score of enhanced variants. Our enhancements of BFWS( f5) outperform SoTA planners, on average solving more problems, more quickly, without using multiple open lists or runs. OL rrp -Dual provides an improved dual-strategy solver, solving more problems than all other tested planners and attaining a meaningfully higher Agile score than BFNoS-Dual, the second-best in coverage.
Figure 1: Number of expansions (x-axis vs. y-axis) (lower is better). Comparing BFWS( f5 ), BFWS( f5 )-ol rrp , and BFWS( f5 )-op rrp . The high-density regions lie below the red line, indicating a systematic improvement over the baseline BFWS( f5 ).
Figure 2: Total solver time (x-axis vs. y-axis) (lower is better). Comparing BFWS( f5 ), BFWS( f5 )-ol rrp , and BFWS( f5 )-op rrp .
Figure 3: Plan cost (Unit action costs) (x-axis vs. y-axis) (lower is better). Comparing BFWS( f5 ), BFWS( f5 )-ol rrp , and BFWS( f5 )-op rrp .
Domain
BFWS( f5 )
BFWS( f5 )-ol rrp
BFWS( f5 )-op rrp
agricola-sat18-strips (20)
10
12 ± 0.6
12 ± 0.8
airport (50)
47
47 ± 0.6
48 ± 0.0
assembly (30)
30
30 ± 0.5
29 ± 0.5
barman-sat14-strips (20)
20
20 ± 0.0
20 ± 0.0
blocks (35)
35
35 ± 0.0
35 ± 0.0
caldera-sat18-adl (20)
15
18 ± 0.6
16 ± 1.0
Table 3: Comparative performance analysis across the full set of benchmark domains. % score is the average of the % of instances solved in each domain. Values for solvers with randomized components represent the mean and include the standard deviation across 5 measurements, using seeds from 0 to 4.
Domain
Dual-
Apx-BFWS
LAMA-
Scorpion
BFNoS-Dual
BFWS t -hlm
BFWS t -hlm
BFWS t -hlm
BFWS t -hlm
BFWS
(Tarski)
First
Maidu
op rrp
ol rrp
ol rrp -UTP
ol rrp -Dual
agricola-sat18-strips
13
18 ± 0.6
12
12
15 ± 0.0
13 ± 1.5
14 ± 1.0
14 ± 0.6
14 ± 0.6
airport
46
47 ± 0.6
34
38
46 ± 0.6
47 ± 0.0
47 ± 0.0
47 ± 0.0
47 ± 0.0
assembly
30
30 ± 0.0
30
30
30 ± 0.0
30 ± 0.0
30 ± 0.0
30 ± 0.6
30 ± 0.0
barman-sat14-strips
20
20 ± 0.0
20
20
20 ± 0.0
20 ± 0.0
20 ± 0.0
20 ± 0.0
20 ± 0.0
blocks
35
35 ± 0.0
35
35
35 ± 0.0
35 ± 0.0
35 ± 0.0
35 ± 0.0
35 ± 0.0
Table 4: Comparative performance analysis across the full set of benchmark domains. % score is the average of the % of instances solved in each domain. Values for solvers with randomized components represent the mean and include the standard deviation across 3 measurements, using seeds from 0 to 2.
Autonomous agents require some form of goal and plan recognition to interact in multiagent settings. Unfortunately, all existing goal recognition datasets suffer from a systematical bias induced by the planning systems that generated them, namely heuristic-based forward search. This means that existing datasets lack enough challenge for more realistic scenarios (e.g., agents using different planners), which impacts the evaluation of goal recognisers with respect to using different planners for the same goal. In this paper, we propose a new method that uses top-k planning to generate multiple, different, plans for the same goal hypothesis, yielding benchmarks that mitigate the bias found in the current dataset. This allows us to introduce a new metric called Version Coverage Score (VCS) to measure the resilience of the goal recogniser when inferring a goal based on different sets of plans. Our results show that the resilience of the current state-of-the-art goal recogniser degrades substantially under low observability settings.
Mustafa F. Abdelwahed, Felipe Meneguzzi Kin Max Piamolini Gusmao, Joan Espasa
University of St Andrews, School of Computer Science, UK · Pontifical Catholic University of Rio Grande do Sul, Brazil · University of Aberdeen, UK
Goal recognition aims to infer an agent's goal from observations of its behaviour. In realistic settings, recognition can benefit from exploiting hierarchical task structure and reasoning under uncertainty. Planning-based goal recognition has made substantial progress over the past decade, but to the best of our knowledge no existing approach jointly integrates hierarchical task structure with probabilistic inference. In this paper, we introduce the first planning-based probabilistic framework for hierarchical goal recognition over Hierarchical Task Networks (HTNs). We instantiate the framework by exploiting an HTN planner with a three-stage generative model for likelihood estimation, yielding posterior distributions over goal hypotheses. Empirical results show improved recognition performance over the existing HTN-based recognizer on HTN benchmarks. Overall, the framework lays a foundation for probabilistic goal recognition grounded in hierarchical planning structure, moving goal recognition toward more practical settings.
Automated Planning is a subfield of Artificial Intelligence (AI) where the main objective is generating a sequence of actions, known as a plan, that helps us reach a goal state from an initial state. A planning problem is defined by a set of objects, an initial state and a desired goal state. The objective is to compute a plan that'll lead us from the inital state to the goal state. Programs that generate plans are called planners. In this paper, we did a complementary study to the state-of-the-art LLM called PlanGPT which was released last year. We redid some experiments to verify whether planning with LLMs is pertinent and worthwhile. We also check whether the results obtained in the official PlanGPT paper for plan coverage were correct, and we also performed a more comprehensive study on PlanGPT's performance: in our paper PlanGPT's performance was evaluated using two metrics: Plan Cost and Plan Generation Time. The results of planGPT were compared to those produced by a traditional planner for the same plans and same metrics. We discovered that PlanGPT is no better than a Greedy search strategy.