# Why Not Use Your Textbook? Knowledge-Enhanced Procedure Planning of
Instructional Videos

Kumaranage Ravindu Yasas Nagasinghe1, Honglu Zhou2, Malitha Gunawardhana1,3,
Martin Renqiang Min2, Daniel Harari4, Muhammad Haris Khan1
1MBZUAI, 2NEC Laboratories, USA, 3 University of Auckland, 4Weizmann Institute
of Science

###### Abstract

In this paper, we explore the capability of an agent to construct a logical
sequence of action steps, thereby assembling a strategic procedural plan. This
plan is crucial for navigating from an initial visual observation to a target
visual outcome, as depicted in real-life instructional videos. Existing works
have attained partial success by extensively leveraging various sources of
information available in the datasets, such as heavy intermediate visual
observations, procedural names, or natural language step-by-step instructions,
for features or supervision signals. However, the task remains formidable due
to the implicit causal constraints in the sequencing of steps and the
variability inherent in multiple feasible plans. To tackle these intricacies
that previous efforts have overlooked, we propose to enhance the agent’s
capabilities by infusing it with procedural knowledge. This knowledge, sourced
from training procedure plans and structured as a directed weighted graph,
equips the agent to better navigate the complexities of step sequencing and
its potential variations. We coin our approach KEPP, a novel Knowledge-
Enhanced Procedure Planning system, which harnesses a probabilistic procedural
knowledge graph extracted from training data, effectively acting as a
comprehensive textbook for the training domain. Experimental evaluations
across three widely-used datasets under settings of varying complexity reveal
that KEPP attains superior, state-of-the-art results while requiring only
minimal supervision. Code and trained model are available at
https://github.com/Ravindu-Yasas-Nagasinghe/KEPP

11footnotetext: Mohamed bin Zayed University of Artificial Intelligence

##  1 Introduction

Figure 1: Expert trajectories [7] of the ‘Make Jello Shots’ task from the
CrossTask dataset [59]. Heavier color indicates more frequently visited path.
This depicts the complexities of the procedure planning task, arising from the
subtle causal links in step sequencing (e.g., steps like ‘stir mixture’ or
‘pour mixture’ typically occur after adding individual ingredients), the
varied probabilities of transitioning between steps, and the diversity in
plans viable for a given starting point and an intended outcome. Motivated by
these nuanced challenges, we propose Knowledge-Enhanced Procedure Planning
(KEPP) with the use of a probabilistic procedure knowledge graph to capture
and represent these intricacies

The evolution of the internet has precipitated an unprecedented influx of
video content, serving as a vital educational resource for myriad learners.
Individuals frequently leverage platforms such as YouTube to acquire new
skills, ranging from culinary arts to automobile maintenance [33]. While these
instructional videos benefit the development of intelligent agents in
mastering long-horizon tasks, the challenge for embodied agents like robots
extends beyond merely interpreting visuals. It requires high-level reasoning
and planning to effectively assist in complex, real-life scenarios [13].

Procedure Planning in Instructional Videos demands an agent to produce a
sequence of actionable steps, thereby crafting a procedure plan that
facilitates the transition from an initial visual observation towards
achieving a desired goal state [9, 7, 46, 55, 50, 49]. The task acts as a
precursor to an envisioned future scenario in which an agent like a robot
provides on-the-spot support, such as assisting an individual in preparing a
recipe. The capacity to perceive the state of the world and devise coherent
action plans in conjunction with or on behalf of humans appears indispensable
in such contexts [6].

Current methods in procedure planning in instructional videos make extensive
use of various annotations available within the datasets to enrich input
features or provide supervisory signals (see Table 1). These include detailed,
temporally localized visual observations of intermediate action steps
throughout the procedure plan [9, 7, 46], high-level procedural task labels
[50, 49], and step-by-step instructions in natural language [55, 49]. Despite
advancements, significant challenges persist, including characterizing the
implicit causal constraints in step sequencing, the varied probabilities of
transitioning between steps, and the inherent variability of multiple viable
plans (see Fig. 1).

To address these intricacies that previous efforts have overlooked, we propose
to enhance the agent’s capabilities in procedure planning by infusing it with
comprehensive procedural knowledge [58], derived from training procedure plans
and structured as a directed weighted graph. This graph, as a Probabilistic
Procedural Knowledge Graph [5] where nodes denote steps from diverse tasks and
edges represent step transition probabilities in the training domain, empowers
agents to more adeptly navigate the complexities of step sequencing and its
potential variations. We coin our proposed approach KEPP, a novel Knowledge-
Enhanced Procedure Planning system that harnesses a probabilistic procedural
knowledge graph (P2KG), constructed from training procedure plans. This graph
functions like a detailed textbook, providing extensive knowledge for the
training domain, and thereby circumventing the need for costly multiple
annotations required by existing methods. Additionally, we decompose the
instructional video procedure planning problem into two parts: one driven by
objectives specific to step perception and the other by a procedural
knowledge-informed modeling of procedure planning. In this problem
decomposition, the first and last action steps are predicted based on the
initial and goal visual states. Following this, a procedure plan is crafted by
leveraging the procedure plan recommendations retrieved from the P2KG. The
recommendations correspond to the most probable procedure plans frequently
used in training, conditioned on the predicted first and last action steps. In
a similar vein to the approach by Li  _et al_. [29], our proposed
decomposition strategy reduces uncertainty by maximizing the use of currently
available information, namely the initial and goal visual states. This allows
for the improvement of procedure planning through more accurate predictions of
start and end actions. Plus, this decomposition effectively incorporates
procedural knowledge into procedure planning, thereby enhancing its
effectiveness.

Our contributions are as follows:

  * •

We propose KEPP, a Knowledge-Enhanced Procedure Planning system for
instructional videos that leverages rich procedural knowledge from a
probabilistic procedural knowledge graph (P2KG). This approach necessitates
only a minimal amount of annotations for supervision.

  * •

We decompose the problem in procedure planning of instructional videos:
predicting the initial and final steps from the start and end visuals, and
then creating a plan using procedural knowledge retrieved based on these
predicted steps. This approach prioritize the currently available information
and effectively incorporates procedural knowledge, enhancing strategic
planning.

  * •

Experimental evaluations conducted on three widely-used datasets, under
settings of varying complexity, reveal that KEPP attains superior, state-of-
the-art results in procedure planning. Code and trained models will be made
publicly available.

##  2 Related Work

Instructional Videos, which demonstrate multi-step procedures, have become a
hotbed of research. The studies delve into various aspects, including
comprehending and extracting intricate spatiotemporal content from video [18,
21, 23, 19, 44, 35, 39, 53, 12, 40, 51], interpreting the interrelationships
between various actions and procedural events [43, 59], and developing
capabilities for forecasting [38, 37] and strategic reasoning and planning
[28] within the context of these videos. Furthermore, by leveraging the
multimodality of visual, auditory, and narrative elements within these videos,
research extends to areas like multimodal alignment [2, 54], grounding [10,
32, 14, 47, 25], representation learning [34, 11, 57], pre-training [26, 58,
15], and more [36, 17, 52, 24]. This paper focuses on procedure planning in
instructional videos.

Procedure Planning is a vital skill for autonomous agents tasked with handling
complex activities in everyday settings. Essentially, these agents must
discern the appropriate actions to reach a specific goal. This aspect of
artificial intelligence (AI) has been a prominent and integral subject in
fields like robotics [42, 41, 28, 20]. Yet, the challenge of procedure
planning in the context of instructional videos is notably distinct, and
potentially more complex, than its counterparts in natural language processing
[30, 8], multimodal generative AI [31, 13], and simulated environments [41,
28, 27]. Its significance is underscored by the need for planning that is
grounded in real-world scenes. This requires the development of AI agents
capable of accurately perceiving and understanding the current real-world
context, and then anticipating and mapping out a logical sequence of actions
to fulfill a high-level goal effectively.

Procedure Planning in Instructional Videos has recently garnered research
attention. DDN [9] initiates this trend by conceptualizing the problem as
sequential latent space planning. Building on this, PlaTe [46] employs
transformers for both action and state models, integrating Beam Search for
enhanced performance. Meanwhile, Ext-GAIL [7] suggests employing contextual
modeling through Variational autoencoder and adversarial policy learning. This
method considers contextual information as time-invariant knowledge, crucial
for distinguishing specific tasks and allowing for multiple planning outcomes.

While these earlier approaches have viewed procedure planning as an
autoregressive sequence generation problem, recent methods regard it as a
distribution-fitting problem to mitigate error propagation in sequential
decisions. In this vein, P3IV [55] replaces intermediate visual states with
linguistic representations for supervision, predicting all steps
simultaneously instead of using autoregressive methods. To circumvent the
complex learning strategies and high annotation costs of previous work, PDPP
[50] models the entire intermediate action sequence distribution using a
conditioned projected diffusion model. This approach redefines the planning
problem as a sampling process from this distribution and simplifies
supervision by using only instructional video task labels. E3P [49], also
encoding task information, adopts a mask-and-predict strategy for mining step
relationships in procedural tasks, integrating probabilistic masking for
regularization. Differing from these methods, our approach does not rely on
annotations of intermediate states, natural language step representations, or
procedural task labels.

Recognizing the difficulties inherent in high dimensional state supervision
and the accumulation of errors in action sequences, SkipPlan [29] was
developed. It strategically focuses on action predictions, breaking down
longer sequences into shorter, more manageable sub-chains by skipping over
less reliable intermediate actions. Drawing inspiration from SkipPlan, our
approach decomposes the procedure planning problem to prioritize the most
reliable information available (ref. § 3.1.2). However, we innovate further by
incorporating a Probabilistic Procedure Knowledge Graph, significantly
enriching the planning phase.

Figure 2:  Overview of our methodology. We introduce KEPP, a Knowledge-
Enhanced Procedure Planning system for instructional videos, leveraging a
Probabilistic Procedural Knowledge Graph (P2KG). KEPP breaks down procedure
planning into two parts: predicting initial and final steps from visual
states, and crafting a procedure plan based on the procedural knowledge
retrieved from P2KG, conditioned on the predicted first and last action steps.
KEPP requires minimal annotations and enhances planning effectiveness

##  3 Methodology

In the following, we will first introduce the problem setup in § 3.1, and
then, we present the details of KEPP, our novel Knowledge-Enhanced Procedure
Planning system, in § 3.2. An overview of KEPP is provided in Fig. 2.

###  3.1 Problem and Method Overview

####  3.1.1 Problem Formulation

We follow the problem definition for procedure planning of instructional
videos put forth by Chang _et al_. [9]: given an observation of the initial
state $v_{start}$ and a goal state $v_{goal}$, both are short video clips
indicating different states of the real-world environment extracted from an
instructional video, a model is required to plan a sequence of action steps
$a_{1:T}$ to reach the indicated goal. Here, $T$ is the planning horizon,
inputting to the model, corresponding to the number of action steps in the
sequence produced by the model so that the environment state can be
transformed from $v_{start}$ to $v_{goal}$. We use $a_{t}$ to denote the
action step at the timestamp $t$, and in the following, $v_{s}$ and $v_{g}$
are short for $v_{start}$ and $v_{goal}$. Mathematically, the procedure
planning problem is defined as $p\left(a_{1:T}|v_{s},v_{g}\right)$ that
denotes the conditional probability distribution of the action sequence
$a_{1:T}$ given the initial visual observation $v_{start}$ and the goal visual
state $v_{goal}$.

####  3.1.2 Problem Decomposition

Considering the initial and final visual states are input, providing the most
reliable information, we hypothesize that predicting the first and final
action steps is more dependable than interpolating the intermediate ones, and
consequently, an enhanced accuracy in predicting the first and final steps can
lead to more effective procedure planning. Inspired by this hypothesis, we
decompose the procedure planning problem into two sub-problems, as shown in
Eq. 9:

$p\left(\hat{a}_{1:T}|v_{s},v_{g}\right)=p\left(\hat{a}_{2:T-1}|\hat{a}_{1},\hat{a}_{T}\right)p\left(\hat{a}_{1},\hat{a}_{T}|v_{s},v_{g}\right),$
(1)

where the first sub-problem is to identify the beginning step $a_{1}$ and the
end step $a_{T}$, and the second sub-problem is to plan the intermediate
action steps $a_{2:T-1}$ given $a_{1}$ and $a_{T}$. We use $\hat{a}_{t}$ to
denote predicted action step at timestamp $t$.

Our proposed problem decomposition in Eq. 9 bears resemblance with the problem
formulation proposed by Li  _et al_. [29]; they decompose procedure planning
into
$p\left(\hat{a}_{1:T}|v_{s},v_{g}\right)=\prod_{t=2}^{T-1}p\left(\hat{a}_{t}|\hat{a}_{1},\hat{a}_{T}\right)p\left(\hat{a}_{1},\hat{a}_{T}|v_{s},v_{g}\right)$.
However, our formulation differs in its approach to modeling the second sub-
problem. Specifically, we employ a conditioned projected diffusion model (ref.
§ 3.2) to jointly predict $a_{2:T-1}$ at once, whereas Li  _et al_. [29] rely
on Transformer decoders to predict each intermediate action independently.
Furthermore, we integrate a probabilistic procedure knowledge graph (ref. §
3.2.2) to address the second sub-problem.

Tackling the second sub-problem is nontrivial even when armed with an oracle
predictor for the first sub-problem. Procedure planning in real-life scenarios
remains daunting because of the following challenges: (1) the presence of
implicit temporal and causal constraints in the sequencing of steps, (2) the
existence of numerous viable plans given an initial state and a goal state,
and (3) the need to incorporate the real-life everyday knowledge both in task-
sharing steps and in managing the inherent variability in transition
probabilities between steps. Previous studies tackled these challenges by
extensively harnessing detailed annotations in the datasets to augment input
features or offer supervision signals (see Table 1). In contrast, we propose
harnessing a Probabilistic Procedural Knowledge Graph (P2KG) which is
extracted from the procedure plans in the training set. With the P2KG at our
hand, we further decompose the procedure planning problem to reduce its
complexity and learn $f_{\theta}:(v_{s},v_{g},T)\rightarrow
p\left(\hat{a}_{1:T}|v_{s},v_{g}\right)$ as follows:

$\begin{array}[]{l}p\left(\hat{a}_{1:T}|v_{s},v_{g}\right)=\\\
p\left(\hat{a}_{1:T}|\tilde{a}_{1:T},v_{s},v_{g}\right)p\left(\tilde{a}_{1:T}|\hat{a}_{1},\hat{a}_{T}\right)p\left(\hat{a}_{1},\hat{a}_{T}|v_{s},v_{g}\right)\end{array}$
(2)

where $f_{\theta}$ denotes the machine learning model, and $\tilde{a}_{1:T}$
represents a graph path (i.e., a sequence of nodes) from P2KG. This retrieved
graph path provides a valuable procedure plan recommendation aligned with the
training domain, thus mitigating the complexity of procedure planning.

It is worth noting that the proposed approach to modeling procedure planning
using Eq. 2 demands only a minimal level of supervision, merely relying on the
ground truth training procedure plan; Eq. 2 circumvents the need for
additional annotations. We describe details of our P2KG-enhanced approach in
the following subsection.

###  3.2 KEPP: Knowledge-Enhanced Procedure Planning

We propose KEPP (Fig. 2) utilizing a probabilistic procedure knowledge graph
extracted from the training set. We firstly identify the beginning and
conclusion steps according to the input initial and goal states; and then,
conditioned on these steps and the planning horizon $T$, we query the graph to
retrieve relevant procedural knowledge for knowledge-enhanced procedure
planning of instructional videos.

####  3.2.1 Identify Beginning and Conclusion Steps

Given $v_{start}$ and $v_{goal}$ as input, we adapt a Conditioned Projected
Diffusion Model [50] (ref. supplementary material) to identify the first
action step and the final step; we refer to this model as the ‘Step
(Perception) Model’.

Standard Denoising Diffusion Probabilistic Model tackles data generation
through a denoising Markov chain over variables $\left\\{x_{N}\ldots
x_{0}\right\\}$, starting with $x_{N}$ as a Gaussian random distribution [22].
In the forward diffusion phase, Gaussian noise
$\epsilon\sim\mathcal{N}(0,\mathbf{I})$ is progressively added to the initial,
unaltered data $x_{0}$, transforming it into a Gaussian random distribution.
Conversely, the reverse denoising process transforms Gaussian noise back into
a sample. Denoising is parameterized by a learnable noise prediction model,
and the learning objective is to learn the noise added to $x_{0}$ at each
diffusion step. After training, the diffusion model generates data akin to
$x_{0}$ by iteratively applying the denoising process, starting from random
Gaussian noise.

Adopting Conditioned Projected Diffusion Model as the Step Model. For our step
model, the distribution we aim to fit is the two-action sequence
$\left[a_{1},a_{T}\right]$, based on the visual initial and goal states,
$v_{start}$ and $v_{goal}$. These conditional visual states are concatenated
with the actions along the action feature dimension, forming a multi-
dimensional array:

$\left[\begin{array}[]{ccccc}\pagecolor{gray!25}v_{s}&\pagecolor{gray!25}0&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}0&\pagecolor{gray!25}v_{g}\\\
a_{1}&\pagecolor{gray!25}0&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}0&a_{T}\end{array}\right]$
(3)

where the array is zero-padded to have a length corresponds to the planning
horizon $T$. During the denoising process, these conditional visual states can
change, potentially misleading the learning process. To prevent this, a
condition projection operation [50] is applied, ensuring the visual state and
zero-padding dimensions remain unchanged (shaded below). The projection
operation can be denoted as follows:

$\footnotesize\left[\begin{array}[]{ccccc}\pagecolor{gray!25}\hat{v}_{1}&\pagecolor{gray!25}\hat{v}_{2}&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}\hat{v}_{T-1}&\pagecolor{gray!25}\hat{v}_{T}\\\
\hat{a}_{1}&\pagecolor{gray!25}\hat{a}_{2}&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}\hat{a}_{T-1}&\hat{a}_{T}\end{array}\right]\xrightarrow[\text{
}]{\text{Projection}}\left[\begin{array}[]{ccccc}\pagecolor{gray!25}v_{s}&\pagecolor{gray!25}0&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}0&\pagecolor{gray!25}v_{g}\\\
\hat{a}_{1}&\pagecolor{gray!25}0&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}0&\hat{a}_{T}\end{array}\right]$
(4)

where $\hat{v}_{t}$ denotes the predicted visual state dimensions at timestamp
$t$ within the planning horizon $T$.

####  3.2.2 Construct the Probabilistic Procedure Knowledge Graph (P2KG)

The Probabilistic Procedure Knowledge Graph [5] $\text{P${}^{2}$KG}=(V,E,w)$
is a directed and weighted graph. In this structure, each step from the
training set is represented as a node. During the graph construction process,
we iterate over the training procedure plans, and for each direct step
transition present in a plan, we add an edge from $a_{t}$ to $a_{t+1}$ if it
does not already exist in the graph; otherwise, we increase its existing
frequency count by one. Eventually, this process results in a frequency-based
Procedural Knowledge Graph (PKG) [58], which adeptly encapsulating the
complexities of step sequencing in procedures and its potential variations,
thereby addressing challenges (1) and (2) of procedure planning (ref. §
3.1.2). To further tackle challenge (3), this graph undergoes a transformation
into a probabilistic format. In this transformed graph, the edges are not just
connections but also signify the likelihoods of transitioning from one step to
another. The weight of an edge from $a_{t}$ to $a_{t+1}$ is the count of
transitions from action step $a_{t}$ to $a_{t+1}$ normalized by total count of
$a_{t}$ being executed [5]. The normalization converts the frequency-based
weight into probability distribution and the sum of all out-going edges is
one.

####  3.2.3 P2KG-Enhanced Procedure Planning

Retrieving Procedure Plan Recommendations from the P2KG. Humans use both
previously-acquired knowledge and external knowledge when solving problems.
The P2KG provides extensive procedural knowledge, serving as a comprehensive
textbook, particularly beneficial for the planning model that requires
advanced skills. To utilize this procedural knowledge, queries are made to the
P2KG using the first ($\hat{a}_{1}$) and last ($\hat{a}_{T}$) actions
predicted by the step model. The aim is to find graph paths no longer than $T$
steps, starting from $\hat{a}_{1}$ and ending at $\hat{a}_{T}$.

This above process often results in multiple possible paths. To evaluate these
paths, the probability of each is calculated by multiplying the probability
weights of the edges along the path. For instance, the probability of a path
$a_{1}\rightarrow a_{2}\rightarrow a_{3}$ is determined by the product
$w_{a_{1}\rightarrow a_{2}}\times w_{a_{2}\rightarrow a_{3}}$. These paths are
then ranked according to their probabilities, and the top $R$ paths are
selected as the recommended procedure plans from the P2KG, where $R$ is
predefined.

For paths shorter than $T$, padding is applied at any point in the middle of
the sequence to explore all possible resultant paths. When $R$ is greater than
one, the top $R$ paths are aggregated through linear weighting into a single
path. This final path is then used as an additional input for the procedure
planning model, thereby enhancing its decision-making process.

Adopting Conditioned Projected Diffusion Model as the Planning Model. For the
planning model, the conditional visual states and the procedure plan
recommendation from the P2KG are concatenated with the actions along the
action feature dimension, forming a multi-dimensional array:

$\left[\begin{array}[]{ccccc}\pagecolor{gray!25}v_{s}&\pagecolor{gray!25}0&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}0&\pagecolor{gray!25}v_{g}\\\
\pagecolor{gray!25}\tilde{a}_{1}&\pagecolor{gray!25}\tilde{a}_{2}&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}\tilde{a}_{T-1}&\pagecolor{gray!25}\tilde{a}_{T}\\\
a_{1}&a_{2}&\ldots&a_{T-1}&a_{T}\end{array}\right]$ (5)

The rest process is similar to the step model, except that the project
operation guarantees that three specific aspects remain unaltered–the
dimensions of the the visual state, P2KG recommendation, and zero-padding.

##  4 Experiments

Models | Required Annotations | $T=3$ | $T=4$
---|---|---|---
step class | visual states | step text | task class | $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$ | $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$
Random | ✓ |  |  |  | $<0.01$ | 0.94 | 1.66 | $<0.01$ | 0.83 | 1.66
Retrieval-Based | ✓ |  |  |  | 8.05 | 23.3 | 32.06 | 3.95 | 22.22 | 36.97
WLTDO [16] | ✓ | ✓ |  |  | 1.87 | 21.64 | 31.70 | 0.77 | 17.92 | 26.43
UAAA [1] | ✓ | ✓ |  |  | 2.15 | 20.21 | 30.87 | 0.98 | 19.86 | 27.09
UPN [45] | ✓ | ✓ |  |  | 2.89 | 24.39 | 31.56 | 1.19 | 21.59 | 27.85
DDN [9] | ✓ | ✓ |  |  | 12.18 | 31.29 | 47.48 | 5.97 | 27.10 | 48.46
PlaTe [46] | ✓ | ✓ |  |  | 16.00 | 36.17 | 65.91 | 14.00 | 35.29 | 55.36
Ext-GAIL wo Aug. [7] | ✓ | ✓ |  |  | 18.01 | 43.86 | 57.16 | - | - | -
Ext-GAIL [7] | ✓ | ✓ |  |  | 21.27 | 49.46 | 61.70 | 16.41 | 43.05 | 60.93
P3IV ♣ [55] | ✓ |  | ✓ |  | 23.34 | 49.96 | 73.89 | 13.40 | 44.16 | 70.01
PDPP ♣ [50] | ✓ |  |  | ✓ | 26.38 | 55.62 | 59.34 | 18.69 | 52.44 | 62.38
E3P ♣ [49] | ✓ |  | ✓ | ✓ | 26.40 | 53.02 | 74.05 | 16.49 | 48.00 | 70.16
SkipPlan [29] ♣ | ✓ |  |  |  | 28.85 | 61.18 | 74.98 | 15.56 | 55.64 | 70.30
Ours w/ P2KG ($R$=2) | ✓ |  |  |  | 22.60 | 48.76 | 53.57 | 13.90 | 45.79 | 55.00
Ours ♣ w/ P2KG ($R$=1) | ✓ |  |  |  | 33.34 | 61.36 | 64.14 | 20.38 | 55.54 | 64.03
Ours ♣ w/ P2KG ($R$=2) | ✓ |  |  |  | 33.38 | 60.79 | 63.89 | 21.02 | 56.08 | 64.15
PDPP ♣ † [50] | ✓ |  |  | ✓ | 37.20 | 64.67 | 66.57 | 21.48 | 57.82 | 65.13
Ours ♣ † w/ P2KG ($R$=1) | ✓ |  |  |  | 38.12 | 64.74 | 67.15 | 24.15 | 59.05 | 66.64
Table 1: Performance of our method in comparison to existing baselines for CrossTask dataset. ♣ means that the input visual features are from the S3D network [34] pretrained on HowTo100M [33]; otherwise, precomputed features provided in CrossTask are used. † indicates the results are under the PDPP’s setting, while others are under the conventional setting  Models | $T=5$ | $T=6$
---|---|---
DDN [9] | 3.10 | 1.20
P3IV ♣ [55] | 7.21 | 4.40
PDPP ♣ [50] | 13.22 | 7.49
E3P ♣ [49] | 8.96 | 5.76
SkipPlan ♣ [29] | 8.55 | 5.12
Ours ($R$=2) | 8.17 | 5.32
Ours ♣ ($R$=1) | 13.25 | 8.09
Ours ♣ ($R$=2) | 12.74 | 9.23
PDPP ♣ † [50] | 13.45 | 8.41
Ours ♣ † ($R$=1) | 14.20 | 9.27
Table 2: Success Rate ($SR^{\uparrow}$) comparison to existing baselines for
CrossTask dataset under longer horizons

###  4.1 Evaluation Protocol

Datasets: In our evaluation, we employed datasets from three sources:
CrossTask [59], COIN [48], and the Narrated Instructional Videos (NIV) [4].
The CrossTask dataset comprises 2,750 video clips, each representing one of 18
distinct tasks, and features an average of 7.6 actions per clip. The COIN
dataset is more extensive, including 11,827 videos across 180 tasks, with an
average of 3.6 actions per video. Lastly, the NIV dataset, though smaller in
scale, includes 150 videos that capture 5 everyday tasks, with a higher
density of actions, averaging 9.5 actions per video. All ablation studies and
analyses were conducted on CrossTask.

Implementation Details: We use two Tesla A100 GPUs for all the experiments. We
chose horizon $T\in\\{3,4,5,6\\}$ and P2KG ($R$=1) condition for
implementation. In some cases, we incorporate P2KG ($R$=2) and LLM conditions
which are indicated in the respective tables. Throughout this study, the P2KG
($R$=1) is employed with a batch size of 256, unless explicitly stated
otherwise. More implementation details are available in the supplementary
material.

Figure 3: Qualitative analysis of the ‘Make Jello Shots’ task Figure 4:
Qualitative analysis of the ‘Change a Tire’ task

Evaluation Metrics: Our study employs mean intersection over union (mIoU),
mean accuracy (mAcc), and success rate (SR) as our evaluation metrics. mIoU
evaluates the overlap between the predicted actions with the ground-truth
actions using IoU by regarding them as two action sets. mAcc is quantified as
the average of the precise correspondences between the predicted actions and
their respective ground truth counterparts at corresponding time steps. Thus,
mAcc counts the order of actions, and is stricter than mIoU. SR is the most
stringent metric, considering a sequence to be successful solely if it
exhibits a perfect match with the ground truth action sequence throughout.

Baselines: We compare our model with widely used state-of-the-art methods:
WLTDO [16], UAAA [1], UPN [45], DDN [9], PlaTe [46], Ext-GAIL [7], P3IV [55],
PDPP [50], SkipPlan [29], and E3P [49]. More details of these methods are
available in the supplementary material. Compared to other models, PDPP uses a
different experimental setting. In PDPP, authors set the window after the
start time of $a_{1}$ and before the end time of $a_{T}$, contrary to the
standard practice of setting a 2-second window around the start and end time
(ref. [9]). We conduct the experiments on both PDPP’s proposed setting and the
conventional setting.

###  4.2 Comparison with the State of the Art (SOTA)

CrossTask (short horizon): We evaluate on CrossTask for short horizons ($T=3$
and $T=4$). According to the results shown in Table 1, our proposed method
outperforms the PDPP in PDPP’s setting in every evaluation metric. More than
0.9% and 2% improvement in success rate in $T=3$ and $T=4$ respectively. In
the conventional setting, our method with both P2KG ($R$=1) and P2KG ($R$=2)
conditions outperform the success rate values by a significant margin compared
to other baselines. P2KG ($R$=2) slightly outperforms P2KG ($R$=1), indicating
potential benefits of incorporating more procedural knowledge from the P2KG.

CrossTask (long horizon): We use long-horizon predictions for $T=5$ and $T=6$
for further evaluating our model as shown in Table 2. In PDPP’s setting (†),
our method improves the success rate in both $T=5$ and $T=6$. In the
conventional setting, our method utilizing P2KG ($R$=1) demonstrates the
highest SR value for $T=5$, and for a longer horizon at $T=6$, our method
delivers superior performance for P2KG ($R$=2). Our method performs well under
the challenging scenario of a long planning horizon.

NIV and COIN: Evaluations of our method on other datasets are shown in Table 3
and Table 4. On NIV, ours achieves the best result under the mIoU metric with
$T$=3, and under both the SR and mIoU metrics with $T$=4. Our method does not
rank as the top performer on COIN. The likely reason is that the COIN dataset
features just an average of 3.6 actions per video–a scenario that does not
necessitate advanced procedural (sequence-level) knowledge. Furthermore, the
dataset’s extensive collection of over 11k videos provides a substantial
resource for baselines to learn basic procedural knowledge. The results on
COIN ($T$=4) is available in the supplementary material.

Models |  NIV ($T$=3) |  NIV ($T$=4)
---|---|---
| $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$ | $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$
Random | 2.21 | 4.07 | 6.09 | 1.12 | 2.73 | 5.84
DDN [9] | 18.41 | 32.54 | 56.56 | 15.97 | 27.09 | 53.84
Ext-GAIL [7] | 22.11 | 42.20 | 65.93 | 19.91 | 36.31 | 53.84
P3IV [55] | 24.68 | 49.01 | 74.29 | 20.14 | 38.36 | 67.29
E3P [49] | 26.05 | 51.24 | 75.81 | 21.37 | 41.96 | 74.90
Ours | 24.44 | 43.46 | 86.67 | 22.71 | 41.59 | 91.49
Table 3: Performance of baselines and ours for NIV dataset Models | COIN
---|---
($T$=3) | $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$
Random | $<0.01$ | $<0.01$ | 2.47
Retrieval | 4.38 | 17.40 | 32.06
DDN [9] | 13.9 | 20.19 | 64.78
Ext-GAIL [7] | - | - | -
P3IV [55] | 15.4 | 21.67 | 76.31
E3P [49] | 19.57 | 31.42 | 84.95
SkipPlan [29] | 23.65 | 47.12 | 78.44
Ours | 20.25 | 39.87 | 51.72
Table 4: Performance of baselines and ours for COIN dataset  Model | T=3 | T=4 | T=5 | T=6
---|---|---|---|---
| SR | mAcc | mIoU | SR | mAcc | mIoU | SR | mAcc | mIoU | SR | mAcc | mIoU
w.o P2KG conditions † | 35.69 | 63.91 | 66.04 | 20.52 | 57.47 | 64.39 | 12.8 | 53.44 | 64.01 | 8.15 | 50.45 | 64.13
Ours † | 38.12 | 64.74 | 67.15 | 24.15 | 59.05 | 66.64 | 14.20 | 53.84 | 65.56 | 9.27 | 50.22 | 65.97
Table 5: Performance of our method with and without P2KG conditions on CrossTask ♣ dataset  Model ($T$=6, CrossTask ♣) | SR | mAcc | mIoU
---|---|---|---
Ours with P2KG ($R$=1)
PDPP setting | 9.27 | 50.22 |  65.97
Conventional setting | 8.09 | 50.80 | 65.39
1 LLM condition
PDPP setting | 7.74 | 50.28 | 64.05
Conventional setting | 7.21 | 49.68 | 63.89
P2KG ($R$=1) and 1 LLM condition
PDPP setting | 8.81 | 49.97 | 65.22
Conventional setting | 8.20 | 51.46 | 64.30
Table 6: Performance of the plan recommendations provided by the probabilistic
procedure knowledge graph v.s. LLM.

###  4.3 Ablation Studies

Ablation on the probabilistic procedure knowledge graph. We analyze the role
of P2KG in improving the performance of our proposed method. Table 5 shows the
results which clearly demonstrate that using P2KG conditions improves the
performance significantly for every $T$ value. Especially when $T=4$, success
rate (SR) improves more than 3% and mean IoU improves more than 2%.

Plan recommendations provided by probabilistic procedure knowledge graph v.s.
LLM. We recognize the recent trend of utilizing LLMs to enhance action
anticipation [56] or planning in other realms [42, 3, 27, 28]. In Table 6, we
compare the results between using P2KG v.s. using LLM (‘llama-2-13b-chat’) to
generate the plan recommendations. By looking at Table 6, we can confirm that
using the P2KG recommendation gives more accurate results than just using the
LLM generated recommendation.

Probabilistic procedure knowledge graph (P2KG) v.s. Frequency-based procedure
knowledge graph (PKG). The probabilistic procedure knowledge graph uses out-
edge normalization to encode step transition probabilities (§ 3.2.2), while
the frequency-based procedure knowledge graph uses min-max normalization over
the frequency counts throughout the graph. In both cases, the planning model
only uses 1 procedure plan recommendation from the graph as condition in our
experimental analysis. By looking at the results shown in Table 7, it is
evident that the probabilistic procedure knowledge graph outperforms the
frequency-based procedure knowledge graph.

Models | SR | mAcc | mIoU
---|---|---|---
Frequency graph | 7.66 | 48.61 | 64.21
Probabilistic graph | 8.09 | 50.80 | 65.40
Table 7: Comparison of the performance between probabilistic procedure knowledge graph v.s. frequency-based procedure knowledge graph for $T$=6 on CrossTask ♣ dataset Condition | SR | mAcc | mIoU
---|---|---|---
without GT data aug. | 38.12 | 64.74 | 67.15
with GT data aug. | 32.45 | 62.42 | 62.80
Table 8: Effect of different input conditions for performance on CrossTask ♣ dataset ($T$=3) in PDPP’s setting  Models | T=3 | T=4 | T=5 | T=6
---|---|---|---|---
| $\hat{a}_{1}$ | $\hat{a}_{T}$ | $\hat{a}_{1}$ | $\hat{a}_{T}$ | $\hat{a}_{1}$ | $\hat{a}_{T}$ | $\hat{a}_{1}$ | $\hat{a}_{T}$
Ours | 53.69 | 50.60 | 55.56 | 52.51 | 55.58 | 51.81 | 57.09 | 51.92
Ours ♣ | 71.42 | 63.32 | 72.98 | 63.37 | 72.42 | 63.29 | 63.82 | 59.96
Table 9: The step model’s start and end step prediction accuracies on the
CrossTask dataset

Effect of utilizing predicted steps for input conditions to train the
procedure planing model. Our proposed problem decomposition allows training
the planning model with ground truth (GT) first and last steps. We experiment
with two ways to train the planning model. Method 1 uses the predicted start
and end steps ($\hat{a}_{1}$ and $\hat{a}_{T}$) as input to generate P2KG
conditions and use them to train the planning model. Method 2 is where we
augment the predicted start and end steps using the GT start and end steps
($a_{1}$ and $a_{T}$) by generating 3 more data samples as follows:
[$\hat{a}_{1}$,$a_{T}$], [$a_{1}$,$\hat{a}_{T}$], and [$a_{1}$,$a_{T}$]. Then
we generate P2KG conditions for each data and train the model. From the
results shown in Table 8, we can see the method without GT data augmentation
shows better results. This suggests that leveraging ground truth data during
training can lead to worse performance during testing. While the step model
does not consistently yield flawless predictions, this experiment validates
the utility of using its predicted steps to train the planning model within
our proposed problem decomposition.

###  4.4 Analyses

Qualitative results. In Figure 3 and Figure 4, we present qualitative examples
of our proposed method. Intermediate steps are padded in the step model
because it only predicts the start and end actions. In the ‘make jello shot’
task shown in Figure 3, the model gives a wrong prediction in the intermediate
steps when using P2KG ($R$=1) condition. However, it predicts correctly when
using P2KG ($R$=2) conditions. In the ‘change a tire’ task shown in Figure 4,
the model is able to predict all the intermediate steps in given conditions.

Figure 5: Example of a sub-graph in our probabilistic procedure knowledge
graph (P2KG) for CrossTask dataset. This graph effectively encapsulates real-
world knowledge of distinct transition probabilities between steps, e.g., the
probability of transitioning from ‘start loose’ to ‘jack up’ is 0.65, in
contrast to a mere 0.14 for the reverse transition–the P2KG reflects the
common real-life practice where loosening the lug nuts before jacking up the
car leads to a safer and more efficient tire change. Figure 6: Expert
trajectories of the ‘Make Jello Shots’ task, involving task-sharing steps and
thus out-of-task step transitions. Thicker lines indicate paths that are more
frequently visited

Visualizations of the probabilistic procedure knowledge graph. In Figure 5, We
show a sub-graph from our probabilistic procedure knowledge graph. This graph
is drawn around the ‘jack up’ node up to the depth of 2 nodes.

Visualizations of the expert trajectories. Figure 6 illustrates the steps
involved in completing the ‘make jello shots’ task, along with their
transitions to other steps within the entire training data. This figure
demonstrates that our P2KG encodes diverse sequencing possibilities for steps
and also captures task-sharing steps across the entire training domain. For
instance, ‘pour water’ is a step in ‘make jello shots’ task, but it can also
be part of other tasks, leading to a step transition from ‘pour water’ to ‘add
fish.’ This structure allows models to leverage rich procedural knowledge.

Results for the step model. Table 9 presents the results of the step model,
indicating potential areas for enhancement to elevate the planning
performance.

##  5 Conclusion

We focus on the formulation of procedural plans from an AI agent in the realm
of instructional videos. We propose to enhance the agent’s capabilities by
incorporating procedural knowledge. This knowledge is gleaned from the
training procedure plans, enabling the agent to adeptly handle the intricacies
of step sequencing and its variations. We term this innovative approach KEPP
(Knowledge-Enhanced Procedure Planning). KEPP employs a probabilistic
procedural knowledge graph, sourced from the training domain, effectively
serving as a ‘textbook’ for procedure planning. Experiments conducted on three
datasets demonstrate that KEPP delivers top-tier performance while
necessitating only a minimal amount of supervision.

## References

  * Abu Farha and Gall [2019] Yazan Abu Farha and Juergen Gall.  Uncertainty-aware anticipation of activities.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops_ , pages 0–0, 2019.
  * Afouras et al. [2023] Triantafyllos Afouras, Effrosyni Mavroudi, Tushar Nagarajan, Huiyu Wang, and Lorenzo Torresani.  Ht-step: Aligning instructional articles with how-to videos.  In _Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track_ , 2023.
  * Ajay et al. [2023] Anurag Ajay, Seungwook Han, Yilun Du, Shaung Li, Abhi Gupta, Tommi Jaakkola, Josh Tenenbaum, Leslie Kaelbling, Akash Srivastava, and Pulkit Agrawal.  Compositional foundation models for hierarchical planning.  _arXiv preprint arXiv:2309.08587_ , 2023.
  * Alayrac et al. [2016] Jean-Baptiste Alayrac, Piotr Bojanowski, Nishant Agrawal, Josef Sivic, Ivan Laptev, and Simon Lacoste-Julien.  Unsupervised learning from narrated instruction videos.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4575–4583, 2016.
  * Ashutosh et al. [2023] Kumar Ashutosh, Santhosh Kumar Ramakrishnan, Triantafyllos Afouras, and Kristen Grauman.  Video-mined task graphs for keystep recognition in instructional videos.  _arXiv preprint arXiv:2307.08763_ , 2023.
  * authors [2023] Anonymous authors.  Active procedure planning with uncertainty-awareness in instructional videos, 2023.  Under review as a conference paper at ICLR 2024. https://openreview.net/pdf?id=JDd46WodYf.
  * Bi et al. [2021] Jing Bi, Jiebo Luo, and Chenliang Xu.  Procedure planning in instructional videos via contextual modeling and model-based policy learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 15611–15620, 2021.
  * Brahman et al. [2023] Faeze Brahman, Chandra Bhagavatula, Valentina Pyatkin, Jena D Hwang, Xiang Lorraine Li, Hirona J Arai, Soumya Sanyal, Keisuke Sakaguchi, Xiang Ren, and Yejin Choi.  Plasma: Making small language models better procedural knowledge models for (counterfactual) planning.  _arXiv preprint arXiv:2305.19472_ , 2023.
  * Chang et al. [2020] Chien-Yi Chang, De-An Huang, Danfei Xu, Ehsan Adeli, Li Fei-Fei, and Juan Carlos Niebles.  Procedure planning in instructional videos.  In _European Conference on Computer Vision_ , pages 334–350. Springer, 2020.
  * Chen et al. [2023] Brian Chen, Nina Shvetsova, Andrew Rouditchenko, Daniel Kondermann, Samuel Thomas, Shih-Fu Chang, Rogerio Feris, James Glass, and Hilde Kuehne.  What, when, and where?–self-supervised spatio-temporal grounding in untrimmed multi-action videos from narrated instructions.  _arXiv preprint arXiv:2303.16990_ , 2023.
  * Dong et al. [2023] Sixun Dong, Huazhang Hu, Dongze Lian, Weixin Luo, Yicheng Qian, and Shenghua Gao.  Weakly supervised video representation learning with unaligned text for sequential videos.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2437–2447, 2023.
  * Doughty et al. [2020] Hazel Doughty, Ivan Laptev, Walterio Mayol-Cuevas, and Dima Damen.  Action modifiers: Learning from adverbs in instructional videos.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 868–878, 2020.
  * Du et al. [2023] Yilun Du, Mengjiao Yang, Pete Florence, Fei Xia, Ayzaan Wahid, Brian Ichter, Pierre Sermanet, Tianhe Yu, Pieter Abbeel, Joshua B Tenenbaum, et al.  Video language planning.  _arXiv preprint arXiv:2310.10625_ , 2023.
  * Dvornik et al. [2022] Nikita Dvornik, Isma Hadji, Hai Pham, Dhaivat Bhatt, Brais Martinez, Afsaneh Fazly, and Allan D Jepson.  Flow graph to video grounding for weakly-supervised multi-step localization.  In _European Conference on Computer Vision_ , pages 319–335. Springer, 2022.
  * Dvornik et al. [2023] Nikita Dvornik, Isma Hadji, Ran Zhang, Konstantinos G Derpanis, Richard P Wildes, and Allan D Jepson.  Stepformer: Self-supervised step discovery and localization in instructional videos.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 18952–18961, 2023.
  * Ehsani et al. [2018] Kiana Ehsani, Hessam Bagherinezhad, Joseph Redmon, Roozbeh Mottaghi, and Ali Farhadi.  Who let the dogs out? modeling dog behavior from visual data.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4051–4060, 2018.
  * Fischer et al. [2022] Sophie Fischer, Carlos Gemmell, Iain Mackie, and Jeffrey Dalton.  Vilt: Video instructions linking for complex tasks.  In _Proceedings of the 2nd International Workshop on Interactive Multimedia Retrieval_ , pages 41–47, 2022.
  * Flanagan et al. [2023] Kevin Flanagan, Dima Damen, and Michael Wray.  Learning temporal sentence grounding from narrated egovideos.  _arXiv preprint arXiv:2310.17395_ , 2023.
  * Fried et al. [2020] Daniel Fried, Jean-Baptiste Alayrac, Phil Blunsom, Chris Dyer, Stephen Clark, and Aida Nematzadeh.  Learning to segment actions from observation and narration.  _arXiv preprint arXiv:2005.03684_ , 2020.
  * Gan et al. [2021] Chuang Gan, Siyuan Zhou, Jeremy Schwartz, Seth Alter, Abhishek Bhandwaldar, Dan Gutfreund, Daniel LK Yamins, James J DiCarlo, Josh McDermott, Antonio Torralba, et al.  The threedworld transport challenge: A visually guided task-and-motion planning benchmark for physically realistic embodied ai.  _arXiv preprint arXiv:2103.14025_ , 2021.
  * Ghoddoosian et al. [2023] Reza Ghoddoosian, Isht Dwivedi, Nakul Agarwal, and Behzad Dariush.  Weakly-supervised action segmentation and unseen error detection in anomalous instructional videos.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10128–10138, 2023.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Advances in neural information processing systems_ , 33:6840–6851, 2020.
  * Hu et al. [2023] Guyue Hu, Bin He, and Hanwang Zhang.  Compositional prompting video-language models to understand procedure in instructional videos.  _Machine Intelligence Research_ , 20(2):249–262, 2023.
  * Huang et al. [2017] De-An Huang, Joseph J Lim, Li Fei-Fei, and Juan Carlos Niebles.  Unsupervised visual-linguistic reference resolution in instructional videos.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 2183–2192, 2017.
  * Huang et al. [2018] De-An Huang, Shyamal Buch, Lucio Dery, Animesh Garg, Li Fei-Fei, and Juan Carlos Niebles.  Finding” it”: Weakly-supervised reference-aware visual grounding in instructional videos.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5948–5957, 2018.
  * Huang et al. [2020] Gabriel Huang, Bo Pang, Zhenhai Zhu, Clara Rivera, and Radu Soricut.  Multimodal pretraining for dense video captioning.  _arXiv preprint arXiv:2011.11760_ , 2020.
  * Huang et al. [2022a] Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch.  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In _International Conference on Machine Learning_ , pages 9118–9147. PMLR, 2022a.
  * Huang et al. [2022b] Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al.  Inner monologue: Embodied reasoning through planning with language models.  _arXiv preprint arXiv:2207.05608_ , 2022b.
  * Li et al. [2023] Zhiheng Li, Wenjia Geng, Muheng Li, Lei Chen, Yansong Tang, Jiwen Lu, and Jie Zhou.  Skip-plan: Procedure planning in instructional videos via condensed action space learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10297–10306, 2023.
  * Lu et al. [2022] Yujie Lu, Weixi Feng, Wanrong Zhu, Wenda Xu, Xin Eric Wang, Miguel Eckstein, and William Yang Wang.  Neuro-symbolic procedural planning with commonsense prompting.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Lu et al. [2023] Yujie Lu, Pan Lu, Zhiyu Chen, Wanrong Zhu, Xin Eric Wang, and William Yang Wang.  Multimodal procedural planning via dual text-image prompting.  _arXiv preprint arXiv:2305.01795_ , 2023.
  * Mavroudi et al. [2023] Effrosyni Mavroudi, Triantafyllos Afouras, and Lorenzo Torresani.  Learning to ground instructional articles in videos through narrations.  _arXiv preprint arXiv:2306.03802_ , 2023.
  * Miech et al. [2019] Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivic.  Howto100m: Learning a text-video embedding by watching hundred million narrated video clips.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 2630–2640, 2019.
  * Miech et al. [2020] Antoine Miech, Jean-Baptiste Alayrac, Lucas Smaira, Ivan Laptev, Josef Sivic, and Andrew Zisserman.  End-to-end learning of visual representations from uncurated instructional videos.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 9879–9889, 2020.
  * Moltisanti et al. [2023] Davide Moltisanti, Frank Keller, Hakan Bilen, and Laura Sevilla-Lara.  Learning action changes by measuring verb-adverb textual relationships.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 23110–23118, 2023.
  * Narasimhan et al. [2022] Medhini Narasimhan, Arsha Nagrani, Chen Sun, Michael Rubinstein, Trevor Darrell, Anna Rohrbach, and Cordelia Schmid.  Tl; dw? summarizing instructional videos with task relevance and cross-modal saliency.  In _European Conference on Computer Vision_ , pages 540–557. Springer, 2022.
  * Nawhal et al. [2022] Megha Nawhal, Akash Abdu Jyothi, and Greg Mori.  Rethinking learning approaches for long-term action anticipation.  In _European Conference on Computer Vision_ , pages 558–576. Springer, 2022.
  * Sener et al. [2022] Fadime Sener, Rishabh Saraf, and Angela Yao.  Transferring knowledge from text to video: Zero-shot anticipation for procedural actions.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * Shah et al. [2023] Anshul Shah, Benjamin Lundell, Harpreet Sawhney, and Rama Chellappa.  Steps: Self-supervised key step extraction from unlabeled procedural videos.  _arXiv preprint arXiv:2301.00794_ , 2023.
  * Shen et al. [2021] Yuhan Shen, Lu Wang, and Ehsan Elhamifar.  Learning to segment actions from visual and language instructions via differentiable weak sequence alignment.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10156–10165, 2021.
  * Shridhar et al. [2020] Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han, Roozbeh Mottaghi, Luke Zettlemoyer, and Dieter Fox.  Alfred: A benchmark for interpreting grounded instructions for everyday tasks.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 10740–10749, 2020.
  * Singh et al. [2023] Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg.  Progprompt: Generating situated robot task plans using large language models.  In _2023 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 11523–11530. IEEE, 2023.
  * Song et al. [2023] Yale Song, Gene Byrne, Tushar Nagarajan, Huiyu Wang, Miguel Martin, and Lorenzo Torresani.  Ego4d goal-step: Toward hierarchical understanding of procedural activities.  In _Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track_ , 2023.
  * Souček et al. [2022] Tomáš Souček, Jean-Baptiste Alayrac, Antoine Miech, Ivan Laptev, and Josef Sivic.  Look for the change: Learning object states and state-modifying actions from untrimmed web videos.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 13956–13966, 2022.
  * Srinivas et al. [2018] Aravind Srinivas, Allan Jabri, Pieter Abbeel, Sergey Levine, and Chelsea Finn.  Universal planning networks: Learning generalizable representations for visuomotor control.  In _International Conference on Machine Learning_ , pages 4732–4741. PMLR, 2018.
  * Sun et al. [2022] Jiankai Sun, De-An Huang, Bo Lu, Yun-Hui Liu, Bolei Zhou, and Animesh Garg.  Plate: Visually-grounded planning with transformers in procedural tasks.  _IEEE Robotics and Automation Letters_ , 7(2):4924–4930, 2022.
  * Tan et al. [2021] Reuben Tan, Bryan Plummer, Kate Saenko, Hailin Jin, and Bryan Russell.  Look at what i’m doing: Self-supervised spatial grounding of narrations in instructional videos.  _Advances in Neural Information Processing Systems_ , 34:14476–14487, 2021.
  * Tang et al. [2019] Yansong Tang, Dajun Ding, Yongming Rao, Yu Zheng, Danyang Zhang, Lili Zhao, Jiwen Lu, and Jie Zhou.  Coin: A large-scale dataset for comprehensive instructional video analysis.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 1207–1216, 2019.
  * Wang et al. [2023a] An-Lan Wang, Kun-Yu Lin, Jia-Run Du, Jingke Meng, and Wei-Shi Zheng.  Event-guided procedure planning from instructional videos with text supervision.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 13565–13575, 2023a.
  * Wang et al. [2023b] Hanlin Wang, Yilu Wu, Sheng Guo, and Limin Wang.  Pdpp: Projected diffusion for procedure planning in instructional videos.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 14836–14845, 2023b.
  * Xu et al. [2020] Frank F Xu, Lei Ji, Botian Shi, Junyi Du, Graham Neubig, Yonatan Bisk, and Nan Duan.  A benchmark for structured procedural knowledge extraction from cooking videos.  _arXiv preprint arXiv:2005.00706_ , 2020.
  * Yang et al. [2021] Yue Yang, Joongwon Kim, Artemis Panagopoulou, Mark Yatskar, and Chris Callison-Burch.  Induce, edit, retrieve: Language grounded multimodal schema for instructional video retrieval.  _arXiv preprint arXiv:2111.09276_ , 2021.
  * Zala et al. [2023] Abhay Zala, Jaemin Cho, Satwik Kottur, Xilun Chen, Barlas Oguz, Yashar Mehdad, and Mohit Bansal.  Hierarchical video-moment retrieval and step-captioning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 23056–23065, 2023.
  * Zhang et al. [2023] Jiahao Zhang, Anoop Cherian, Yanbin Liu, Yizhak Ben-Shabat, Cristian Rodriguez, and Stephen Gould.  Aligning step-by-step instructional diagrams to video demonstrations.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2483–2492, 2023.
  * Zhao et al. [2022] He Zhao, Isma Hadji, Nikita Dvornik, Konstantinos G Derpanis, Richard P Wildes, and Allan D Jepson.  P3iv: Probabilistic procedure planning from instructional videos with weak supervision.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2938–2948, 2022.
  * Zhao et al. [2023] Qi Zhao, Ce Zhang, Shijie Wang, Changcheng Fu, Nakul Agarwal, Kwonjoon Lee, and Chen Sun.  Antgpt: Can large language models help long-term action anticipation from videos?  _arXiv preprint arXiv:2307.16368_ , 2023.
  * Zhong et al. [2023] Yiwu Zhong, Licheng Yu, Yang Bai, Shangwen Li, Xueting Yan, and Yin Li.  Learning procedure-aware video representation from instructional videos and their narrations.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 14825–14835, 2023.
  * Zhou et al. [2023] Honglu Zhou, Roberto Martín-Martín, Mubbasir Kapadia, Silvio Savarese, and Juan Carlos Niebles.  Procedure-aware pretraining for instructional video understanding.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10727–10738, 2023.
  * Zhukov et al. [2019] Dimitri Zhukov, Jean-Baptiste Alayrac, Ramazan Gokberk Cinbis, David Fouhey, Ivan Laptev, and Josef Sivic.  Cross-task weakly supervised learning from instructional videos.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3537–3545, 2019.

Supplementary Material

Unless otherwise mentioned, all the results and analysis are obtained for the
CrossTask dataset with input visual features from the S3D network [34]
pretrained on HowTo100M [33]. We organize the Supplementary Materials as
follows:

A. Further Experimental Results

A.1 Additional Results on COIN and NIV

A.2 Parameter Sensitivity Analysis

B. More Thorough Analysis

B.1 More Qualitative Results

B.2 More Visualizations of the P2KG

B.3 Training Efficiency

B.4 Analysis by the Step Transition Heatmap

B.5 Limitations and Failure Cases

C. Method and Implementation Details

C.1 Diffusion Model Details

C.2 Implementation of KEPP

C.3 Implementation of Ablations

C.4 Baselines

## A. Further Experimental Results

### A.1 Additional Results on COIN and NIV

COIN. We present the performance of our method in comparison to several
baseline approaches on the COIN dataset across different planning horizons in
Table S.1. While the results demonstrate that our method outperforms the
majority of previous literature, it does not secure the top position when
considering small planning horizons ($T$=3 or $T$=4) for the COIN dataset.
This can be attributed to the fact that the COIN dataset typically consists of
only 3.6 actions per video on average, a scenario where advanced sequence-
level procedural knowledge is not essential. The advantage of our method
becomes increasingly pronounced as the planning horizon expands. With a larger
planning horizon ($T$=5), our method significantly outperforms the previous
state-of-the-art (SOTA) methods, achieving a performance gain of $6.16$ on the
most strict metric, Success Rate (SR), compared to SkipPlan [29]. Our method’s
utilization of plan recommendations from the Probabilistic Procedure Knowledge
Graph (P2KG) effectively reduces the complexity of long-horizon planning.

NIV. Previous works did not provide results for the NIV dataset concerning
long-horizon procedural planning; in Table S.2. we evaluate our model’s
performance in comparison to the PDPP model [50] specifically on the NIV
dataset for long-horizon procedural planning ($T$=5 or $T$=6). (For results
regarding short-horizon planning, please refer to Table 3 in the main paper.)
Our model demonstrates superior performance in terms of the SR, mAcc, and mIoU
metrics.

Models |  COIN ($T$=3) |  COIN ($T$=4) |  COIN ($T$=5)
---|---|---|---
| $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$ | $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$ | $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$
Random | $<0.01$ | $<0.01$ | 2.47 | $<0.01$ | $<0.01$ | 2.32 | - | - | -
Retrieval | 4.38 | 17.40 | 32.06 | 2.71 | 14.29 | 36.97 | - | - | -
DDN [9] | 13.9 | 20.19 | 64.78 | 11.13 | 17.71 | 68.06 | - | - | -
P3IV [55] | 15.4 | 21.67 | 76.31 | 11.32 | 18.85 | 70.53 | 4.27 | 10.81 | 68.81
E3P [49] | 19.57 | 31.42 | 84.95 | 13.59 | 26.72 | 84.72 | - | - | -
SkipPlan [29] | 23.65 | 47.12 | 78.44 | 16.04 | 43.19 | 77.07 | 9.90 | 38.99 | 76.93
Ours ($R$=2) | 20.25 | 39.87 | 51.72 | 15.63 | 39.53 | 53.27 | 16.06 | 40.72 | 56.15
Table S.1: Performance of baselines and ours on the COIN dataset. Our method excels at handling challenging planning scenarios that demand longer planning horizons ($T$); with $T$=5, ours achieves a performance gain of 6.16 on the most strict metric, Success Rate (SR)  Models |  NIV ($T$=5) |  NIV ($T$=6)
---|---|---
| $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$ | $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$
PDPP [50] | 18.95 | 37.26 | 87.50 | 14.94 | 41.02 | 93.70
Ours ($R$=2) | 21.58 | 39.79 | 91.66 | 17.53 | 43.62 | 93.75
Table S.2: Performance of baselines and ours on the NIV dataset. Our method demonstrates superior performance on all metrics Model | $SR^{\uparrow}$ | $mAcc^{\uparrow}$ | $mIoU^{\uparrow}$
---|---|---|---
PDPP [50] | 18.69 | 52.44 | 62.38
Ours ($R$=1) | 20.38 | 55.54 | 64.03
Ours ($R$=2) | 21.02 | 56.08 | 64.25
Ours ($R$=3) | 20.22 | 56.19 | 63.15
Ours ($R$=4) | 20.76 | 55.63 | 64.22
Ours ($R$=5) | 20.37 | 55.43 | 63.93
Table S.3: Parameter sensitivity study on the CrossTask dataset. Performance
of our method initially increases and then decreases as $R$ continues to
increase. An excessively large value for $R$ may lead to the inclusion of less
prominent paths in the conditions given to the planning model

(a)

(b)

Figure S.1: Probabilistic Procedure Knowledge Graphs (P2KG) around the nodes
‘peel banana’ and ‘add whipped cream’ respectively up to a two-node depth.
P2KG effectively captures the task-sharing steps, variability in transition
probabilities between steps, implicit temporal and causal relationships of
steps, as well as the existence of numerous viable plans given an initial step
and an end step

(a) Add Oil to Your Car task

(b) Build Simple Floating Shelves task

(c) Make French Toast task

(d) Make Meringue task

Figure S.2: Qualitative Analysis of Different Procedural Tasks. In the
illustration, ‘P2KGC =1’ and ‘P2KGC =2’ indicates the first and second paths
obtained from the probabilistic procedure knowledge graph respectively

### A.2 Parameter Sensitivity Analysis on the Number of Plan Recommendations

Our proposed method involves querying a probabilistic procedure knowledge
graph; this process extracts the most probable graph paths, which have
specified start and end steps. These paths are subsequently considered as
recommended procedural plans and are employed as additional input conditions
for the model, with the aim of improving its overall performance in procedure
planning. Consequently, the number of plan recommendations, denoted as $R$ in
the main paper, emerges as a novel hyper-parameter in our methodology.

We have conducted a parameter sensitivity analysis to examine the effect of
the number of paths selected from the probabilistic procedure knowledge graph
to be given as conditions to the planning model on the procedure planning
performance. Table S.3 displays the parameter sensitivity of our method with
respect to $R$ on the CrossTask dataset for the planning horizon $T$=4. To
maintain simplicity in implementation, in cases where $R$ exceeds one, we
aggregate the features of the top $R$ graph paths through a linear weighting
process (i.e., weighted summation). This results in consistent feature
dimensions compared to when $R$=1. The weighting scheme is as follows:
$R=1\xrightarrow{}weights:1\newline
R=2\xrightarrow{}weights:\frac{2}{3},\frac{1}{3}\newline
R=3\xrightarrow{}weights:\frac{3}{5},\frac{1}{5},\frac{1}{5}\newline
R=4\xrightarrow{}weights:\frac{4}{7},\frac{1}{7},\frac{1}{7},\frac{1}{7}\newline
R=5\xrightarrow{}weights:\frac{5}{9},\frac{1}{9},\frac{1}{9},\frac{1}{9},\frac{1}{9}\newline
$ where the weights of the graph paths, starting with the most probable one,
are provided above. The weights are empirically determined to emphasize the
top one probable path by assigning it greater weight, and equal weights are
distributed among the remaining graph paths.

Our method, with $R$=2, achieves the best results in SR and mIoU (see Table
S.3). In general, performance of our method initially increases and then
decreases as $R$ continues to increase. The reason for larger values of $R$
yielding lower SR is attributed to the influence of less prominent paths being
included in the conditions given to the planning model. Further tuning of the
weighting scheme could potentially yield even more superior results which we
leave for future work.

## B. More Thorough Analysis

### B.1 More Qualitative Results

Figure S.2 presents more qualitative results of our method compared with PDPP
[50] across a range of procedural tasks, with a planning horizon set at $T$=4.
In scenarios depicted in Figure S.2 (a), (c), and (d), the PDPP model
erroneously predicts the initial or final steps based on the given visual
states, resulting in procedural planning failures. Our approach, however,
incorporates a specialized step model designed to accurately predict these
crucial first and last steps. Furthermore, Figure S.2 highlights how our
method benefits from the plan recommendations provided by the probabilistic
procedure knowledge graph. These recommendations offer invaluable insights
into feasible plans identified during training, thereby significantly
enhancing our method’s capability in procedure planning at test time.

### B.2 More Visualizations of the Probabilistic Procedure Knowledge Graph

Figure S.1 (a) and (b) show the sub-graphs in our probabilistic procedure
knowledge graph (P2KG) around the nodes ‘peel banana’ and ‘add whipped cream’
up to a two-node depth respectively. P2KG effectively captures the task-
sharing steps, variability in transition probabilities between steps, implicit
temporal and causal relationships of steps, as well as the existence of
numerous viable plans given an initial step and an end step.

Figure S.3: Training efficiency comparison between PDPP [50] and our model
(KEPP). These training and validation profiles demonstrate that our model
exhibited significantly faster training convergence compared to PDPP. Our
method with $R$=2 has faster convergence compared to $R$=1. The arrows
indicate the epochs of convergence determined by the early stopping scheme

### B.3 Training Efficiency

Figure S.3 compares the training convergence of our planning model with PDPP
[50]. We have plotted the loss values across the training epochs and indicated
the epoch of convergence determined by the early stopping scheme. Our model,
with $R$=2 and $R$=1, converged at the 30th and 40th epochs, respectively,
while the previous state-of-the-art method, PDPP, converged at the 60th epoch.
Our model exhibited significantly faster training convergence compared to
PDPP. The training efficiency of our method is achieved by leveraging the
probabilistic procedure knowledge graph, which provides valuable context to
facilitate the model’s learning process.

(a) Train

(b) Test

(c) Ours (R=1)

Figure S.4: Step Transition Heatmaps on the CrossTask dataset of (a) the
training set, (b) the testing set, and (c) procedure plan predictions made by
our method on the test set. The i-row-j-column depicts the probability of the
transition from i-th action to j-th action. Darker color indicates higher
probability. Please refer to Section B.4 for details regarding task and action
names

### B.4 Analysis by the Step Transition Heatmap

Figure S.4 visualises the step transition matrices of the ground-truth
training procedure plans, ground-truth testing procedure plans, and procedure
plan predictions made by our method with $R$=1 on the test set, for the
‘Change a Tire’ task on the CrossTask dataset. The i-row-j-column depicts the
probability of the transition from i-th action step to j-th action step.
Darker color of the step transition heatmap indicates higher probability. The
steps depicted in the heatmaps in order are: “brake on”:1, “get things out”:2,
“start loose”:3, “jack up”:4, “unscrew wheel”:5, “withdraw wheel”:6, “put
wheel”:7, “screw wheel”:8, “jack down”:9, “tight wheel”:10, “put things
back”:11, “remove funnel”:12, “lower jack”:13, “put funnel”: 14, “wipe off
dipstick”: 15, “close cap”:16, “insert dipstick”:17, “pour oil”:18, “pull out
dipstick”:19, “raise jack”:20, “remove cap”:21.

Out of the 21 actions illustrated, first 11 actions belong to the ‘Change a
Tire’ task while other actions are from several other tasks but highly
relevant to the ‘Change a Tire’ task (e.g., ‘raise jack”:20 and “lower
jack”:13). When comparing Figure S.4 (a) and (b), the distributions of action
step transitions differ between training and testing. When comparing Figure
S.4 (b) and (c), our method, which utilizes graph-structured training
knowledge, reasonably predicts the step transition matrix on the test set.

(a)

(b)

(c)

Figure S.5: Failure Cases: (a) when repetitive smaller action sequences exist
within the procedure plan, (b) when $a_{1}$ and $a_{T}$ have not been
accurately predicted by the step model, and (c) when the start and end action
steps are the same, and the probabilistic procedure knowledge graph fails to
provide valuable plan recommendations because it overly encodes the repetitive
actions

### B.5 Limitations and Failure Cases

Figure S.5 illustrates three distinct failure case patterns in our model: (a)
failure in prediction when repetitive smaller action sequences exist within
the procedure plan, (b) failure in accurately predicting $a_{1}$ and $a_{T}$
from the step model, and (c) failure in generating valuable probabilistic
procedure knowledge graph paths because the graph overly encodes the
repetitive actions when the start and end action steps are the same.
Consistent with prior studies, cases involving repetitive actions or action
sequences continue to pose challenges. Future studies could consider
addressing these challenging scenarios.

The failure case analysis highlights the limitations of our approach. Our
method depends on the precise prediction of both the initial and final steps
by the step model, and it performs more effectively when the probabilistic
procedure knowledge graph can offer valuable contextual information.

## C. Method and Implementation Details

We will publicly release our code and trained models.

### C.1 Diffusion Model Details

Standard Diffusion Model. A standard denoising diffusion probabilistic model
[22] tackles data generation by establishing the data distribution
$p\left(x_{0}\right)$ through a denoising Markov chain over variables
$\left\\{x_{N}\ldots x_{0}\right\\}$, starting with $x_{N}$ as a Gaussian
random distribution.

In the forward diffusion phase, Gaussian noise
$\epsilon\sim\mathcal{N}(0,\mathbf{I})$ is progressively added to the initial,
unaltered data $x_{0}$, transforming it into a Gaussian random distribution.
Each noise addition step is mathematically defined as:

$x_{n}=\sqrt{\bar{\alpha}_{n}}x_{0}+\epsilon\sqrt{1-\bar{\alpha}_{n}}$ (6)
$q\left(x_{n}|x_{n-1}\right)=\mathcal{N}\left(x_{n};\sqrt{1-\beta_{n}}x_{n-1},\beta_{n}\mathbf{I}\right)$
(7)

where $\bar{\alpha}_{n}=\prod_{s=1}^{n}\left(1-\beta_{s}\right)$ represents
the noise magnitude, and $\\{\beta_{n}\in(0,1)\\}_{n=1}^{N}$ denotes the pre-
defined ratio of Gaussian noise added in each step.

Conversely, the reverse denoising process transforms Gaussian noise back into
a sample. Each denoising step is mathematically defined as:

$p_{\theta}\left(x_{n-1}|x_{n}\right)=\mathcal{N}\left(x_{n-1};\mu_{\theta}\left(x_{n},n\right),\Sigma_{\theta}\left(x_{n},n\right)\right)$
(8)

where $\mu_{\theta}$ is parameterized as a learnable noise prediction model
$\epsilon_{\theta}\left(x_{n},n\right)$, optimized using a mean squared error
(MSE) loss
$L=\left\|\epsilon-\epsilon_{\theta}\left(x_{n},n\right)\right\|^{2}$, and
$\Sigma_{\theta}$ is calculated using $\left\\{\beta_{n}\right\\}_{n=1}^{N}$.
During training, the model selects a diffusion step $n\in[1,N]$, calculates
$x_{n}$ via Eq. 6, then the learnable model estimates the noise and computes
the loss based on the actual noise added at step $n$. After training, the
diffusion model generates data akin to $x_{0}$ by iteratively applying the
denoising process, starting from random Gaussian noise.

Conditioned Projected Diffusion Model. As we incorporate conditional
information into the data distribution, these conditional guides can be
altered during the denoising process. However, modifying these conditions can
lead to incorrect guidance for the learning process, rendering conditional
guides ineffective. To tackle this issue, the Conditioned Projected Diffusion
Model has been introduced to ensure that guided information remains unaffected
during denoising. In this approach, Wang et al. [50] introduce a condition
projection operation within the learning process. Specifically, they enforce
that visual observation conditions and additional condition dimensions remain
unchanged during both training and inference by assigning them to their
initial values. We have adapted their Conditioned Projected Diffusion Model as
the architecture for both our step model and planning model in KEPP.

### C.2 Implementation of KEPP

The step model for $a_{1}$ and $a_{T}$ predictions and the planning model for
procedure plan full-sequence prediction are trained separately. As mentioned
in the main paper, for the step model, intermediate actions are padded in
order to accurately predict $a_{1}$ and $a_{T}$. We use a U-Net based
Conditioned Projected Diffusion Model [50] $f_{\theta}(x_{n},n)$ as the
learnable model architecture for both of the step model and the planning
model, and the training loss is:

$\textit{L}=\sum_{n=1}^{N}(f_{\theta}(x_{n},n)-x_{0})^{2}$ (9)

where $x_{0}$ denotes the initial, unaltered input and N denotes the total
number of diffusion steps.

In line with the approach taken in [50], given that $a_{1}$ and $a_{T}$ are
the most relevant actions for the provided input visual states, we have
modified the training loss by implementing a weighted MSE loss. This involves
multiplying the loss by a weight matrix to give more emphasis to the
predictions of $a_{1}$ and $a_{T}$. For the step model, we have chosen a
weight of 10 for both $a_{1}$ and $a_{T}$. In the case of the planning model,
we have assigned a weight of 5 to $a_{1}$ and $a_{T}$ because the condition
dimensions of intermediate steps in the probabilistic procedure knowledge
graph path has a more significant impact on generating the full action step
sequence. The default value in this weight matrix is 1.

The batch size is 256 for all the experiments. Our training regimen
incorporates a linear warm-up strategy that is tailored to suit the varying
scales of different datasets. For the results of models utilizing the
precomputed features provided in CrossTask, we use 200 for the diffusion step
and train the progress through a total of 12,000 training steps. The learning
rate is gradually escalated to reach 8 × 10-4 over the initial 4,000 steps.
Subsequent to this phase, we implement a learning rate reduction to 4 × 10-4
when reaching the 10,000th step.

When working with the S3D network-extracted features on the CrossTask dataset,
the model similarly starts with a diffusion step of 200 but extends the
training duration to 24,000 steps. The learning rate here ascends linearly to
5 × 10-4 within the first 4,000 steps, followed by a decay factor of 0.5
applied sequentially at the 10,000th, 16,000th, and 22,000th steps.

The NIV dataset, given its smaller size, necessitates a shorter training cycle
of 6,500 steps, starting from a diffusion step of 50. We increase the learning
rate linearly to 3 × 10-4 up until step 4,500, then introduce a decay by 0.5
at step 6,000.

For the COIN dataset, which is significantly larger in scale, the model
undergoes an extended training sequence of 160,000 steps with the diffusion
set at 200. Here, the learning rate experiences a linear surge to 1 × 10-5
within the first 4,000 steps. We implement a decay rate of 0.5 at the 14,000-
and 24,000-step marks. After this point, the learning rate is maintained at a
constant 2.5 × 10-6 for the remainder of the training process.

When obtaining mIoU, for CrossTask dataset we compute IoU on every single
action sequence and calculates the average of these IoUs to obtain mean IoU
similar to method used in [50]. For COIN and NIV datasets, we compute mIoU on
every mini-batch (batch size = 256) and calculate the average as the result
similar to the approach used in [55].

In the scenario where paths from the probabilistic procedure knowledge graph
are available between $\hat{a}_{1}$ and $\hat{a}_{T}$ but it does not match
the desired number of paths ($R$), then repetition of already available paths
are considered to meet the desired path requirement. In scenarios where the
combination of $\hat{a}_{1}$ and $\hat{a}_{T}$ does not result in the
inclusion of a path from the probabilistic procedure knowledge graph, the
graph paths ($P$) are formulated as follows:

$\text{Path Variations
($L$)}=[[[\hat{a}_{1}]^{T-M}.[\hat{a}_{T}]^{M}],[[\hat{a}_{1}]^{M}.[\hat{a}_{T}]^{T-M}]]$
$\text{Generated Paths
($P$)}=[L[i\mod\text{len}(L)]\,\text{for}\,i\,\text{in}\,\text{range }(R)]$

where $T$ is the planning horizon, $M=T//2$, and path variations ($L$) are the
two types of possible combinations of $\hat{a}_{1}$ and $\hat{a}_{T}$. For
example if horizon (T) equals 5, then the path variations (L) possible are
[[$\hat{a}_{1}$, $\hat{a}_{1}$, $\hat{a}_{1}$, $\hat{a}_{T}$, $\hat{a}_{T}$],
[$\hat{a}_{1}$, $\hat{a}_{1}$, $\hat{a}_{T}$, $\hat{a}_{T}$, $\hat{a}_{T}$]].
So if one path ($R=1$) is required as the condition for the planning model,
generated path is [$\hat{a}_{1}$, $\hat{a}_{1}$, $\hat{a}_{1}$, $\hat{a}_{T}$,
$\hat{a}_{T}$], and if 2 paths are required ($R=2$) as the condition for the
planning model, generated paths are [$\hat{a}_{1}$, $\hat{a}_{1}$,
$\hat{a}_{1}$, $\hat{a}_{T}$, $\hat{a}_{T}$], and [$\hat{a}_{1}$,
$\hat{a}_{1}$, $\hat{a}_{T}$, $\hat{a}_{T}$, $\hat{a}_{T}$], and if 3 paths
are required ($R=3$) as the condition for the planning model, generated paths
are [$\hat{a}_{1}$, $\hat{a}_{1}$, $\hat{a}_{1}$, $\hat{a}_{T}$,
$\hat{a}_{T}$], [$\hat{a}_{1}$, $\hat{a}_{1}$, $\hat{a}_{T}$, $\hat{a}_{T}$,
$\hat{a}_{T}$], and [$\hat{a}_{1}$, $\hat{a}_{1}$, $\hat{a}_{1}$,
$\hat{a}_{T}$, $\hat{a}_{T}$] likewise. The generated paths ($P$) are then
aggregated through linear weighting into a single path to be given to the
planning model as mentioned in Section A.2 Parameter Sensitivity Analysis on
the Number of Plan Recommendations A.2.

### C.3 Implementation of Ablations

Ablation on the probabilistic procedure knowledge graph. When the
probabilistic procedure knowledge graph is not included as a condition, the
model simplifies only to the planning model, ignoring the step model for
generating $\hat{a}_{1}$ and $\hat{a}_{T}$. In this scenario, the planning
model generates the action sequences using a diffusion process conditioned
solely on the start and end visual observations.

Plan recommendations provided by the probabilistic procedure knowledge graph
and LLM. To enhance the action prediction, we could incorporate LLM generated
action sequence as a condition to our planning diffusion model as shown in
Table 6 in the main paper. To generate the LLM action sequence we use the
‘llama-2-13b-chat’ model and query the model with the prompt:

“In the multi-step task that I am going to perform, I know {total_steps} steps
are required, the first step is {start_action}, and the last step is
{end_action} and I need to go from {start_action} to {end_action}. Can you
tell me the {total_steps} steps in the form ”Step 1, ..., Step {total_steps}”
so that I can follow in order to complete this {total_steps}-step task? Note
that repetitive steps are possible”.

In the above text prompt, ‘total_steps’ indicates the planning horizon, while
‘start_action’ denotes the step model-predicted start action $\hat{a}_{1}$ and
‘end_action’ denotes the step model-predicted end action $\hat{a}_{T}$. For a
single [$\hat{a}_{1},\hat{a}_{T}$] pair occurring in the training or testing
phase, we query the LLM three times and obtain the optimal action for each
step in the sequence by finding the action with the highest occurrence. Then,
the optimal sequence is queried back into the LLM for post-processing to check
the realistic nature of the generated action sequence. The text prompt used
for post-processing verification is as follows:

“Is the following action sequence possible? Note that repetitive steps are
possible. Please answer only ”Yes” or ”No”: {steps}”.

Here, ‘{steps}’ denotes the the generated steps from the first prompt. We then
map the action steps generated from the LLM to the step vocabulary space of
the given dataset. Specifically, the generated action steps from the LLM, as
well as all of the possible action steps from the dataset, are embedded into a
vector space utilizing the ‘bert-base-uncased’ model. For each action in the
LLM-generated sequence, its semantically closest action step from the dataset
is found in the vector space using the K-nearest neighbor (K=1) approach. The
resulting generated action sequence is given as an additional input condition
to the planning model similar to the P2KG condition.

In the situation where both the P2KG and LLM conditions are used for the
planning model, the conditional visual states, LLM recommendation and the
procedure plan recommendation from the P2KG are concatenated with the actions
along the action feature dimension, forming a multi-dimensional array:

$\left[\begin{array}[]{ccccc}\pagecolor{gray!25}v_{s}&\pagecolor{gray!25}0&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}0&\pagecolor{gray!25}v_{g}\\\
\pagecolor{gray!25}\tilde{a}_{1}&\pagecolor{gray!25}\tilde{a}_{2}&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}\tilde{a}_{T-1}&\pagecolor{gray!25}\tilde{a}_{T}\\\
\pagecolor{gray!25}a^{*}_{1}&\pagecolor{gray!25}a^{*}_{2}&\pagecolor{gray!25}\ldots&\pagecolor{gray!25}a^{*}_{T-1}&\pagecolor{gray!25}a^{*}_{T}\\\
a_{1}&a_{2}&\ldots&a_{T-1}&a_{T}\par\end{array}\right]$ (10)

where $\tilde{a}_{i}$ denotes the action from the P2KG at $i^{th}$ step and
$a^{*}_{i}$ denotes the action generated from LLM at $i^{th}$ step.

Probabilistic procedure knowledge graph (P2KG) and Frequency-based procedure
knowledge graph (PKG). The frequency-based procedure knowledge graph (PKG)
performs min-max normailization for the entire graph, and the optimal path
between two nodes is the maximum weighted path. The path weight is calculated
by summing all the individual edge weights between the two nodes. The
probabilistic procedure knowledge graph (P2KG) has undergone output edge
normalization, where the summation of probabilities of all the output paths
from a node is 1. For example, if a node has four output edges (self-loop
edges are also considered as output edges), and the weights along the edges
are $w_{1},w_{2},w_{3},w_{4}$, then the probability of each edge is:
$\frac{w_{1}}{w_{1}+w_{2}+w_{3}+w_{4}},\frac{w_{2}}{w_{1}+w_{2}+w_{3}+w_{4}},\frac{w_{3}}{w_{1}+w_{2}+w_{3}+w_{4}},\frac{w_{4}}{w_{1}+w_{2}+w_{3}+w_{4}}$
respectively. The process of obtaining the highest probable path between two
nodes is explained in Section 3.2.3 of the main paper.

### C.4 Baselines

In the current study, we benchmark our proposed approach against several
established state-of-the-art methods to conduct a comprehensive evaluation.
Below, we describe the methods that serve as our baseline comparisons.

Random Strategy: This naive approach involves the stochastic selection of
actions from the set of possibilities within the dataset to generate procedure
plans.

Retrieval-based Technique: Upon receiving the visual observational inputs,
this method employs a nearest-neighbour algorithm, leveraging the least visual
feature space distance within the training corpus to extract a corresponding
sequence of actions as the procedural blueprint.

WLTDO [16] [‘CVPR 2018’]: Implemented via a recurrent neural network (RNN),
this method sequentially forecasts the necessary actions based on the supplied
pair of observations.

UAAA [1] [‘ICCV workshop 2019’]: Standing for a two-phased strategy, UAAA
integrates an RNN with a Hidden Markov Model (HMM) to autoregressively
estimate the sequence of actions.

UPN [45] [‘ICML 2018’]: This path-planning algorithm is tailored for the
physical realm and acquires a plannable representational form for making
informed predictions.

DDN [9] [‘ECCV 2020’]: The DDN framework operates as a dual-branch
autoregressive model, honing in on an abstracted representation of action
sequences to anticipate the transitions between states and actions in the
feature space.

PlaTe [46] [‘RA-L 2022’]: An advancement of DDN, the PlaTe model incorporates
transformer modules within its dual-branch architecture to facilitate
prediction.

Ext-GAIL [7] [‘ICCV 2021’]: Ext-GAIL addresses procedural planning through
reinforcement learning and decomposes the problem into a dual-stage challenge.
The initial stage in Ext-GAIL is designed to yield time-invariant contextual
information for the subsequent planning phase.

P3IV [55] [‘CVPR 2022’]: A transformative single-branch model, P3IV enriches
its structure with a mutable memory repository and an additional generative
adversarial network. It is capable of concurrently predicting the entire
action sequence during the inference stage.

PDPP [50] [‘CVPR 2023’]: PDPP conceptualizes the task of procedure planning in
instructional videos as analogous to fitting a probabilistic distribution.
Echoing the P3IV, PDPP employs a holistic approach during the inference stage
by forecasting the entire sequence of action steps concurrently.

SkipPlan [29] [‘ICCV 2023’]: Consider procedure planning as a mathematical
chain problem. This model decomposes relatively long chains into multiple
short sub-chains by bypassing unreliable intermediate actions. This transfers
long and complex sequence functions into short but reliable ones.

E3P [49] [‘ICCV 2023’]: This uses procedural task (referred as ‘event’ in
[49]) information for procedure planning by encoding task information into the
sequential modeling process. E3P infers the task information from the observed
states and then plans out actions based on both the states and the predicted
task/event.