Conformal Prediction for Semantically-Aware Autonomous Perception in Urban Environments
Authors: Achref Doula
Tobias Güdelhöfer
Max Mühlhäuser
Alejandro Sanchez Guinea
Venue: CoRL 2024 (2024)
Keywords: Uncertainty in Robotics
Robot Perception
Semantics for Robotics

Abstract: We introduce Knowledge-Refined Prediction Sets (KRPS), a novel approach that performs semantically-aware uncertainty quantification for multitask-based autonomous perception in urban environments. KRPS extends conformal prediction (CP) to ensure 2 properties not typically addressed by CP frameworks: semantic label consistency and true label coverage, across multiple perception tasks. We elucidate the capability of KRPS through high-level classification tasks crucial for semantically-aware autonomous perception in urban environments, including agent classification, agent location classification, and agent action classification. In a theoretical analysis, we introduce the concept of semantic label consistency among tasks and prove the semantic consistency and marginal coverage properties of the produced sets by KRPS. The results of our evaluation on the ROAD dataset and the Waymo/ROAD++ dataset show that KRPS outperforms state-of-the-art CP methods in reducing uncertainty by up to 80\% and increasing the semantic consistency by up to 30\%, while maintaining the coverage guarantees.

Conformal Prediction for Semantically-Aware Autonomous Perception in Urban Environments
Achref Doula
Tobias Güdelhöfer
Max Mühlhäuser Alejandro Sanchez Guinea Telecooperation Lab Technical University of Darmstadt, Germany (doula, max, sanchez] Stk. wwaddaaaatt.....
Abstract:
We introduce Noowledge-Refneee Prediction Sets (KRPS), a novel approach that performs semantically-awar uncertainty quantification for multitask-based au- tonomous perception in urban environments. KRPS extends conformal prediction (CP) to ensure properties not typically addressed by CP frameworks: semantic label consistency and true label coverage, across multiple perception tasks. We elucidate the capability of KRPS through high-level classification tasks crucial for semantically autonomous perception in urban environments, including agent classification, agent location classification, and agent action classification. In theoretical analysis, we introduce the concept of semantic label consistency among tasks and prove the semantic consistency and marginal coverage properties the produced sets by KRPS. The results our evaluation on ROAD dataset and the Waymo/ROAD++ dataset show that KRPS outperforms state-of-the-ie CP methods in reducing uncertainty by up 80% and increasing the semantic consistency by up to 30%, while maintaining the coverage guarantees.
Keywords: Robot Perception, Uncertainty in Robotics, Semantics for Robotics
Introduction
In urban environments, autonomous systems are tasked with navigating complex and dynamic scenes, necessitating robust decision-making mechanisms that interpret diverse elements with high-level semantic understanding. To reason about the scene, autonomous systems perform a ries of critical tasks, distinguishing between different types of agents like pedestrians and vehicles, understanding their actions such walking, turning, or stopping, and identifying their locations relative to key infrastructure like crosswalks and intersections [1, 2, 3, 4, 5, 6]. Such tasks require the construction of semantic relationships between scene elements to ensure safety and enhance model interpretability [7, 8, 9]. However, the inherent unpredictability of urban environments and the safety-critical applications of autonomous perception in urban environments make essential to integrate semantically aware reasoning with uncertainty quantification. Combining semantic and uncertainty awareness allows autonomous agents to make reliable and contextually appropriate de- cisions, adapting to the urban landscape dynamically.
Conformal prediction (CP) [10, 11, 12] emerges as versatile approach for uncertainty quantifica- tion in learning-based models. Compared to other uncertainty quantification frameworks in deep learning, such Bayesian networks [13], Radial Basis Functions networks [14], and evidential learning [15], CP provides uncertainty-ane
predictions by generating prediction sets that are theo- retically guaranteed to include the correct class with user-defined confidence. The guarantees offered by Ca-based frameworks ensure the reliability of the underlying systems, property that is much needed to improve trust and large-scale adoption of autonomous systems interacting with urban environments. CP has been effectively applied in various areas of robotics, including robot manipu-
8th Conference Robot Learning (CoRL. 2024), Munich, Germany.

---

Traditional CP
KRPS
Location: ('OutgoLane's 'IncomLane",
Location: ('IncomLame', 'BusStop')
IncomCycLame" 'Jun', 'BusStop')
Action of "MoeTow", 'Mov', 'Xing', 'Incatif'' 'Incuthhe', "TurLft, 'TuRRht'. WaitZX, XingFmLR. 'iingFmRhh")
Action ('MoxTow', 'Stop')
Agent class: [ear Bus}
Uncertainty: High
Uncertainty: Low
Semantic Consistency: Low
Semantic Consistency: High
(a) Situation
(b) Traditional CP
(c) KRPS
Figure I:
An example of refined sets using KRPS scene from the ROAD dataset [1]. KRPS
reduces the location set size by 60% and the action set size by 80%. In addition to the set size reduction, the produced classes semantically consistent with the predicted agent classes: large vehicle and Bus. More qualitative examples are presented in Appendix D.
lation [16], human-robot interaction [17, 18), autonomous perception [19, 20, 21J. and autonomous navigation [22, 23].
The separate application of traditional CP to different tasks does not guarantee semantic consistency. In our context, semantic consistency refers the logical alignment of predictions across different tasks, ensuring that the inferred attributes are contextually appropriate and mutually compatible, To illustrate this, present in Figure 1b the result of one of our experiments the ROAD dataset [1], where an autonomous agent uses three distinct models to classify an agent, its location, and its action. Applying traditional CP to each task in isolation results in high uncertainty and low semantic consistency. High uncertainty is shown by the numerous potential classes of actions and locations. Low semantic consistency is seen in the conflicting locations (e.g.. incoming cycle lane) and actions (e.g., crossing) for the agent classes (i.e., large vehicle and bus). It is important to note that simply removing inconsistent classes compromises CP coverage guarantees, which undesirable.
In this work, we address the construction of conformal prediction sets across various classification tasks for perception, such as agent, action, and location classification, while ensuring conformal prediction validity and semantic consistency among the produced sets for each task. We propose Knowledge-Refinee Refined Prediction Sets (KRPS), a novel CP approach that reduces uncertainty in au- tonomous agents urban environments by producing valid, uncertainty aware prediction sets that semantically consistent across multiple tasks. KRPS consists of knowledge graph that links the different tasks, and sequential' construction procedure based on intial task ensure the pro- duced sets for subsequent tasks cover the true label with a user-defined probability. The sequential processing of tasks in KRPS allows for efficient on-demand refinement of subsequent task predic- tions, based on initial task results. As depicted in Figure Ic, KRPS sequentially refines the prediction sets for the location and action tasks using the prediction sets from the agent classification task and a knowledge graph. In this case, KRPS leads to more semantically consistent results, reflected by the alignment between the agent classes, its possible locations, and actions, and leads 80% lower uncertainty when compared to traditional CP, reflected by the lower number of classes in the predic- tion sets. In cases where the knowledge graph is incomplete, KRPS manages corner cases, such as anomalies where vehicles are located on sidewalks, by outputting empty prediction sets, indicating the absence of semantically consistent labels. We provide a theoretical analysis of KRPS, intro- ducing the concept of conditional semantic consistency for multitask- autonomous perception and demonstrating the semantic consistency and marginal coverage properties of the produced sets. We evaluate KRPS on large-scale autonomous driving datasets, namely the ROAD dataset [1] and Waymo/ROAD++ dataset [24], from the scope of high-level perception tasks that are crucial for semantically aware autonomous perception and high-level reasoning in urban settings: object class, location, and action. The results of our evaluation show that KRPS outperforms state-of-the-arr con- formal prediction approaches in reducing the uncertainty of the models by up to 80% and increasing the semantic consistency by up to 30%, through the generation of smaller prediction sets that are semantically consistent through the tasks while holding the coverage guarantees.
'Sequentiality in context means refining predictions for one task time.

---

2 Background on Conformal Prediction
We focus on CP for classification, as it is the relevant task for our work. Let go be a classifier pre-trained on dataset Dirain. The model ge outputs estimated probabilities for each class (e.g.. softmax scores), such that go [0, 1]s, where X is an imput image and K the number of classes considered.
Assumption. CP assumes the existence of exchangeable unseen pairs of data examples that are drawn from the same data distribution as Dtrain, to which we refer to as calibration set Deat- The goal of CP is to construct prediction sets for unseen data samples ((tte))) that are valid, i.c., they contain the true label Yesst with a probability 1 a, where is user-defined error rate. This property is called marginal coverage and is expressed in Equation
PelYes C'Xtest) 2
(I)
To construct the prediction sets, CP requires test statistic called non-conformity score S(X, Y), which measures the dissimilarity between predictions generated for an unseen data point and the training data. Based on S. the elements of Deat are ranked, and the empirical calculated. For novel Xtest, for which Yrest unknown test time, C(Xrest) is constructed as ((Xtes))) = {Y S(X,Y) /) This procedure be expressed through p-values that measure the probability of non-conformity, formalized in Theorem 2.1.
a quantile is
Theorem 2.1 (Conformal Prediction [10]) Let Dtrain. Deat, and Xtest be sets of exchangeable random variables. Let S be non-conformity score and a be a user-defined error rate. The set C(Xteat) defined as ((ete))) = (Y E y p--value (Xteett teat. Y)) 2 a} satisfies the marginal coverage property stated in Equation 1.
Knowledge-Refined Prediction Sets
We address the problem of autonomous perception for urban scene understanding based on the reasoning across multiple high-level tasks, that allow the agent to make uncertainty-awar and se- mantically consistent predictions. We focus on 3 classification tasks: agent type, agent location, and agent action, that are deemed necessary to achieve high-level semantic understanding of the robot's 's environment [1, 2, 3, 4]. We assume the existence of 3 separate neural networks g" g', and gd that output the agent class Ve E y², agent location class y E y", and agent action class Y E )", respectively, given a bounding box around the agent of interest Xy, where X₁ E X. and X' represents the set of all agents of interest in a scene. Given the models g".g'. and g", a calibration set Deat, and an unseen test sample Xtest- our goal is to sequentially construct the prediction sets (i(ste for location classification, and C. Ca (Xtett) for action classification, given a (e(test)) that was generated by an agent classification CP algorithm. We opt for sequential task refinement as permits on-demand processing of subsequent tasks in of need. We desire our generated sets to have two properties. The first property is marginal coverage described in Equation 1, which means that the predicted sets are guaranteed to include the true label Ytest with probability of at least - a. The second property is semantic consistency, which means that the prediction sets for each of the classification tasks need to account for classes included in other sets. For example, for C.(X.est) = (car, medium vehicle, large vehicle) is clear that Yrest corresponds to a vehicle, and so (X should not include locations that are not proper to vehicles, such as sidewalk. Traditional CP set-ups do not guarantee these properties, as they only consider one task. In this work, propose knowledge-refined prediction sets (KRPS), a CP-based approach that constructs the prediction sets described above given an initial task and a knowledge graph. For the remain- der of this paper, we refer to sets constructed by KRPS by CKRPS (Xtest). C. CKKPP((Xest) and C: (ettP((((s))) (test).
KRPS consists of two components: knowledge graph and a knowledge-based multitask conformal prediction algorithm. The knowledge graph models the semantic relationships between the different tasks consider. For particular agent class, only subset of all possible locations and actions can

---

be assigned. The other component of our approach is the knowledge-refined multitask conformal prediction algorithm that leverages the knowledge graph to sequentially construct prediction sets for each task, that are semantically consistent while satisfying the coverage guarantees. The semantic consistency is ensured through a knowledge-based pruning procedure that removes location and action classes if they are semantically inconsistent with the agent class.
Knowledge Graph Construction. To construct knowledge-refined prediction sets (KRPS), we build knowledge graph K. in order to model the semantic relationships between the tasks. The knowledge graph in our implementation draws from common sense and available labels in large-scale datasets for urban scene understanding, such as the ROAD and Waymo/ROAD++ datasets [1, 24], as we detail in Appendix B. Using the labels for each task, the semantic rela- tionships between the tasks constructed as follows. Given a task Te and Ta referring to the tasks of agent classification and agent action classification, AC contains set-valued deterministic func- tion Mo ) + 23d that maps agent class labels to the set of all possible action labels, as it is depicted in Figure 2a. Figure 2b shows an example of this mapping, where the class cyclist is mapped to all its possible locations by Me-st, and to all its possible actions by Mc Given K,, we introduce the notion of conditional semantic consistency between prediction sets for each task.
Definition 3.1 (Conditional Semantic Consistency) Let Cj and C. be 2 prediction sets containing class candidates for the tasks T and T', respectively. C2 is semantically consistent with respect to Cj and K., if:
E C,,Y,, E C E Ma))(Y))
(2)
Equation 2 implies that every element in C, has a pre-image in Cj by the semantic mapping Mi-jj- Note that with this definition, Cj can have elements that do not have images in C..
KRPS Construction Procedure. KRPS is based on sequentially pruning prediction sets using knowledge from K. For a given scene and an object Xtest, we start by constructing the predie- tion set for the agent class task CKRPP CX Since our approach is sequential, the construction procedure of the prediction set for the first task follows the usual CP procedure based on Theo- rem 2.1. Next, we acquire all possible locations of agent classes in C RPS (X(eess)))) using the se- mantic mapping from the knowledge graph K.
Algorithm 1: KRPS Procedure
Input
K: knowledge graph.
TI..Tn set of tasks.
MT.T semantic mappings.
M: correction procedure.
Deat: calibration set.
at user-defined error rate.
Output: C RPSS i [1, m]: semantically
consistent prediction sets.
CRRPs y0
To
The set of all possible locations that correspond 2 Pr. + 1.VYT: E ETTi , [0,m] C.K CKRPS (Xtest) is O = MM- RPS We
3 for i == 1 1 m do
use OF as a starting set for further pruning, in- stead of considering the full space of labels y' The pruning consists of a conformal prediction step based on a conformity score proper the lo- cation classification task. Examples of such con- 8 formity scores are 1 - Softmaz. The conformal prediction step produces the set C. Apply- 10 end for ing the steps described above results in a multi- end for hypotheses testing problem, where the family- wise error increases. To account for the MHT problem, applying correction procedure M of the p- p-values is required, as we detail in Appendix A. Prediction sets for further tasks can be acquired by applying the same procedure sequentially using CR Using the procedure explained above, the generated sets guaranteed to be semantically consistent and to have coverage as formalized in Equation 1. The KRPS set construction proce-
4
O --M (CKPPS)
CT CKRPS +
for y E C do PT, +M(p-value(Xrest Deal)) if Py, > a then CK RPS + Ct,
CRPS {g}
return C. CKRPS
; E [1.m]
Ma-st is point to set mapping. We abuse the notation to indicate the set of images for every elements in C. Rrs using the mapping Mc+ti.

---

Semantle Mapping Mo+((X;)
Set of all possible locations for agent X;
Locations
In outgolng eyele lane In incoming cycle lane Al Crossing.
My-(Cyyclitt
Agent X,
Cvelist
Semantic Mapping Mo-aa (Xi)
Set all possible actions for agent X;
Actions
Moving Away Moving Towards Crossing.... ..
(CyolCy
(a) General structure of the knowledge graph.
(b) Knowledge graph for the agent class Cyclist.
Figure 2: Knowledge-gret sewwedde-ggrahhaee structure used in KRPS. Figure 2a shows the structure of the knowledge graph with the semantic mappings (agent - location) } and {agent - action). Figure 2b depicts an example graph for the agent class Cyclist. The full construction procedure is in Appendix B.
dure is formalized in Theorem 3.1 and described in Algorithm 1. The proof of Theorem 3.1 and its corollary, along with analysis of their practical implications, provided in Appendix A.
Reffind Refined Conformal Prediction) Given 2 tasks Te and To the mantic mapping function Mo-ii and the prediction sets (Xtst) and Ot (" the set CKRPS (Xtest) C¹ (Xtest) n Mc-x(Y(est) is semantically consistent with respect to C CRRPS and Kc, and satisfies the marginal coverage described in Equation 3.
Theorem 3.1 (Knowledge-
PlYtest C.K (Xtest) 2
We prove this property by leveraging the probability conservation of the deterministic semantic mappings between the task and proposing a generalizing the cascaded CP Theorem [25] to cover multitask settings. We present the detailed proof of Theorem 3.1 Appendix A.
Corollary 3.1 (Transitivity of conditional semantic consistency) Let CKRPS, C.RPS and CR be 3 prediction respect to CKRPS and K. and C is semantically consistent, with respect CKRPS and K, then and C CPRP is semantically consistent, with respect to C RPS and K.
constructed using KRPS. If CKRPS is semantically consistent, with
We prove the transitivity property by leveraging the semantic consistency between prediction sets of subsequent tasks, guaranteed by Theorem 3.1. We present a proof of Corollary 3.1 in Appendix A.
Evaluation
To support the theoretical results for guaranteed coverage and semantic consistency across different tasks executed sequentially, we evaluate KRPS on 2 large-scale urban scene understanding datasets. We compare the performance of KRPS against 3 baselines including state-of-the-arr approaches, using 2 widely used CP metrics: deviation from coverage rate and set size. Since the first to consider semantic consistency across tasks in CP, we introduce a metric for semantic consistency.
4.1 Datasets
The ROAD Dataset [1]. The Road Event Awareness dataset (ROAD) for autonomous driving in- cludes 22 videos, and 1.7M labels across 11 agent classes, 15 locations, and 23 actions under various weather conditions, providing diverse and challenging set of scenarios for testing the effectiveness of KRPS. ROAD offers (agent, location, action) triplets, ideal for comprehensive evaluation.
The Waymo/ROAD++ Dataset'. The Waymo/ROAD++ dataset, an extension of the ROAD dataset, incorporates 3.5M agents, 4.3M actions, and 4. 4.2M locations from the expansive Waymo autonomous driving dataset [24], annotated with road events akin to those in the ROAD dataset.
Implementation. For the evaluation, classification task, outputting softmax scores. The model is trained on each dataset for 30 epochs
the 3D-RetinaNet [1] with separate heads for each
WWymo/ROAA++: https: sctps://sites. htt::/siiissggllllleeeees www.ww/wwwwwwddee.eeee.ceccceae plus dataset
5

---

with an Adam optimizer at a learning rate of Ir = 0.001. We randomly divide the validation splits of both datasets in 3 equal-sized portions as follows: eval split / for validation, eval split for calibration, and eval split 3 for testing. All experiments use Bonferroni correction for prediction robustness, with results averaged over 100 trials on single 24GB RTX 3090.*
4.2 Metrics
Deviation from Target Coverage (DTC). The deviation from the target coverage rate (DTC) quan- tifies the discrepancy between the achieved coverage, CoVapprouch and the desired target coverage, Coutarget
a, as defined in Equation 4.
DTC Couapproach - CoUtarget
(4)
Negative DTC values indicate coverage below a, indicating failure to meet the theoretical lower bound. DTC values nearing zero suggest that the actual coverage closely aligns with the target coverage. Smaller positive values denote accurate coverage rates above the desired threshold.
Set Size (SS). We measure the average set size provided by KRPS. As providing the full set of labels would be trivial output for CP-based methods achieve the coverage guarantees, smaller set size demonstrates better predictive efficiency.
Conditional Semantic Consistency (SC). We introduce a novel metric to measure the semantic consistency between the generated sets predicted for the task T with respect to T and K. For prediction set Crs, semantic consistency represents the rate of semantically consistent classes the entire and formulated Equation 5. A higher semantic consistency value demonstrates better coherence between the prediction sets across the tasks.
((Y: Y Cr. n MT
:Y:YEC
SC(CT,|CT-I,,))
ICT1
4.3 Baselines
Inspired by recent CP works, such as [26, 25], we evaluate KRPS with the Least Ambiguous Set Classifier (LAC), for which the scoring function is 1 Softmax [27], and 2 state-of-the-as CP scores. The first approach is adaptive predictive sets (APS) [28], which is scoring technique known to improve conditional coverage. The second approach is regularized adaptive predictive sets (RAPS) [29], which is known generate notably smaller predictive sets. RAPS stands unparalleled in minimizing the size of prediction sets. Thus, it is crucial to explore the effectiveness of KRPS in further compressing the predictive set sizes relative to those generated by RAPS.
4.4 Tasks
Our evaluation considers 3 tasks both datasets, namely agent, location, and action elassification. Since our approach acts sequentially multiple tasks, the first task is not refined, which makes the construction of the prediction set for the first task (i.e., agent classification). coincide with the underlying CP process. The task sequences we consider are: (agent + location) and {agent > action). To conduct our evaluation, we first construct the prediction sets for the agent classification using Sof flmaa, APS, and RAPS. Using the predicted agent class sets, we report the results for subsequent tasks: location classification, and action classification. In Appendix C, We report the results of longer task sequences using 3 tasks show the capability to handle longer sequences of tasks with different orders.
4.5 Comparison with State-of-the-Art
We conduct our evaluation using different values of a ranging from 0.1 to 0.5 with a step of 0.1. We present the results on the ROAD and Waymo/ROAD++ datasets in Table la and Table 1b, re-
Our code is available here: https://gitlab. cow/achref.ecceoooooocccoooo d/krps.

---

Task
Score
Method
= 0.1
=
0.2
= 0.1
SS
DTC
SC
DTC
SC
DTC
SC
Softmax
Stundard
7.07
0.05
0.81
6.04
0.10
0.79
4.51
0.19
0.77
KRPS
5,86
0.02
1,00
4.93
0.05
1.00
3.75
0.09
1.00
Location
APS
Standard
7.12
0.80
6.07
0.10
0.79
4.61
0.20
0.76
KRPS
5.90
0.02
1.00
4.96
0.05
1,00
3.65
0.12
1,00
Stundard
2,66
0.07
0.89
2.03
0.15
0.93
1.56
0.34
0.96
RAPS
KRPS
1.00
0.13
1,00
0.13
1.00
Stundurd
7,48
0.01
0.79
5.98
0.01
0.78
3.77
0.06
0.77
Softmax
KRPS
5.83
0.00
1,00
4.70
0.00
1,00
3.06
0.00
1,00
Action
APS
Stundadd
9.77
0.75
8.01
0.10
0.73
5.72
0.30
KRPS
7.29
0.02
1.00
6.01
0.03
1,00
4.35
0.11
1,00
Standard
4.67
0.07
0.84
3.94
0.13
0.87
2.54
0.25
0.92
RAPS
KRPS
3.82
0.03
1.00
3.26
0.02
1.00
2.22
0.15
1.00
(a) Results on the ROAD datasct for for a
(0.1.0.2 0.4).
Bold designates better performance.
0.1
0.2
0.44
Task
Score
Method
ss
DTC
SC
SS
DTC
SC
SS
DTC
SC
Standard
8.10
0.05
0.80
6.04
0.11
0.73
4.13
0.21
0.72
Softmax
KRPS
6.02
0.01
1.00
5.42
0.03
1.00
3.07
0.08
1.00
Standard
9.02
0.07
0.79
7.92
0.10
0.76
4.03
0.22
0.71
Location
APS
KRPS
7.50
0.01
1.00
5.99
0.06
1.00
3.24
0.14
1.00
Standard
2.45
0.09
0.87
2.07
0.15
0.91
1.83
0.34
0.96
RAPS
KRPS
2,01
0.04
1.00
2.04
0.10
1.00
1.17
0.09
1.00
Standard
9.32
0.06
0.80
7.20
0.08
0.78
5.00
0.15
0.81
Softmax
KRPS
6.09
0.01
1.00
4.17
0.03
1.00
3,50
0.10
1.00
Action
APS
Standard
10.41
0.05
0.77
6.84
0.13
0.74
5,36
0.12
0.78
KRPS
5.98
0.02
1,00
4.18
0.02
1.00
3.87
0.12
1,00
Standard
4.36
0.06
0.87
3.03
0.15
0.89
1.50
0.24
0.94
RAPS
KRPS
3.57
0.04
1.00
2.88
0.02
1.00
1.07
1.00
(b) Results on the Waymw/RAA+++ dataset for for a = 0.2,
Bold designates better performance.
Table I: Results of our experiments. Based on the prediction sets for the agent classification task, prediction sets for the location and action are sequentially inferred using KRPS with 3 scoring functions: Softmaz, APS, and RAPS. The standard mode refers to the baseline without KRPS.
spectively. Due to space constraints, we only report the results for a [0.1, 0.2, 0.4]. in the main manuscript. Results for the full set of a values and different task sequences are in Appendix C.
The results show that KRPS substantially reduces the set size for all underlying scores. For the location classification task, the average set size reduction is by 17% for softmax, 18% for APS, and 10% for RAPS, for the ROAD dataset, and by 20% for softmax, 20% for APS, and 27% for RAPS, for the ROAD++ dataset. For the action classification task, the set size reduction achieved by KRPS is more apparent and equals 24% for softmax, 25% for APS, and 16% for RAPS, for the ROAD dataset. For the Waymo/ROAD+ dataset, the results show that KRPS achieved a set size reduction by 36% for softmax, 38% for APS, and 15.4% for RAPS. The contribution of KRPS to set size reduction is particularly apparent for APS, in both datasets. The reason is that APS built to achieve class-wise coverage to account for unbalanced classes in the dataset, which has the effect of increasing the set size. The application of KRPS succeeds in reducing the set size while holding the marginal coverage guarantees. KRPS holds the theoretical coverage guarantees for all values of and for all the non-conformity scores, which is indicated by positive DTC values. Furthermore, KRPS adjusts the coverage rate for all scoring functions, leading to lower DTC values.
KRPS holds conditional semantic consistency guarantees as well, achieving 100% of conditional semantic consistency in all experimental conditions. Compared to the baselines, KRPS increases the conditional semantic consistency in the task of location classification by an average of 26% for softmax, 23% for APS, and 6% for RAPS, for the ROAD dataset, and by 26% for softmax, 23% for APS, and 6% for RAPS, for the ROAD++ dataset. For the task of action classification on the ROAD dataset, KRPS increased the semantic consistency by 25% for softmax, 24% for APS, and 8% for RAPS. For the Waymo/ROAD++ dataset as well, KRPS increases the semantic consistency rates for action prediction by 25.5% for softmax, 31% for APS, and 11% for RAPS. We present more experiments longer task sequences, the influence of the knowledge graph size, and the percentage of the empty sets in Appendices B, and E, respectively.
7

---

Discussion
Recent studies have underscored the importance of incorporating semantics [30, 31, 32, 33] and uncertainty [34, 35, 36, 37] into robotic decision-making frameworks, particularly as Large Lan- guage Models (L..Ms) are increasingly used to enhance autonomous navigation [38, 39, 40, 41]. These models, prone to uncertainty and hallucinations [42], necessitate detailed contextual under- standing of the scene for effective operation [43]. Incorporating semantic awareness and uncertainty awareness enhances both the reliability and interpretability of these systems, addressing a fundamen- tal challenge in their widespread adoption: trust [44, 45]. KRPS introduces a novel approach that combines these aspects to improve the overall efficacy of autonomous decision-making processes. KRPS represents the first approach that extends CP to a multitask learning setup without specific requirements regarding the nature or sequencing of tasks. The theoretical analysis and the empirical evaluation show that KRPS significantly reduces uncertainty, while ensuring semantic consistency, in dynamic urban environments. Furthermore, KRPS benefits from the inherent practicalities of CP, eliminating the need for continual model retraining. Instead, KRPS requires only a computationally efficient calibration process to integrate new data, assuming data exchangeability as per CP norms.
Limitations. As we see KRPS as practical approach to consider uncertainty and semantic aware- ness in autonomous robots and systems, it important to consider the limitations of its application. KRPS, being CP-based approach, traditionally relies on the assumption of data exchangeabil- ity. This assumption can limit its effectiveness with scoring functions that fail to address out-of- distribution (OOD) data scenarios. To mitigate this, KRPS has been designed to be agnostic to the scoring function, as demonstrated in our empirical analysis, making it compatible with OOD-aware calibration procedures, such as [46, 47, 12]. The effectiveness of KRPS is also contingent on the in- tegrity of the underlying knowledge graph. Ambiguities within the knowledge graph regarding class definitions can compromise prediction accuracy. To address this, our evaluation integrates ontologi- cal structures derived from the datasets utilized, such ROAD and Waymo [1, 24], and aligns with [2], facilitating more precise semantic interpretations. Moreover, KRPS is designed to identify and respond to these ambiguities by generating empty prediction sets to effectively manage scenarios not fully covered by the knowledge graph. This feature highlights cases requiring further scrutiny and ensures that KRPS maintains reliability despite incomplete on- tologics. KRPS a sequential approach, leveraging prediction sets from the initial task to generate semantically consistent sets for subsequent tasks. Its dependence on the quality of the first set is intrinsic. Although joint prediction set construction is viable [48], the sequential process allows for on-demand refinements exclusively for the relevant agents in the scene, leading better efficiency.
established logical frameworks
Practicality. While our paper focuses on 3 high-level perception tasks for urban scene understand- ing, KRPS can be extended to other robot perception applications. The formulation of Algorithm and Theorem 3.1 is adaptable to diverse environmental contexts. For example, KRPS can be ap- plied to urban search and rescue, handling sequences of tasks under high uncertainty like victim detection, hazard identification, and robot action selection. Other use-cases can also be envisioned, such robot manipulation, where robot is tasked to recognize and sort objects of different sizes and put them in their corresponding places. KRPS provides uncertainty quantification and semantic consistency at each stage, ensuring accurate object classification, optimal grasp strategy selection, and precise object placement. We elaborate more on these applications in Appendix F.
6 Conclusion
We introduced KRPS, a Knowledge-Refined Prediction Set approach, tailored for multitask learn- ing in urban scene understanding. By refining prediction sets through semantic relationships among tasks, KRPS ensures semantic consistency and adheres to coverage guarantees by producing sig- nificantly smaller prediction sets. KRPS shows promise for real-world applications, particularly in autonomous driving. Due to safety concerns, initial tests were limited to realistic, and challenging datasets. Future work should focus on integrating KRPS into operational systems, with rigorous safety validations and controlled real-world trials to ensure trustworthy autonomous navigation.
8

---

Acknowledgments
This work has been partially funded by the German Federal Ministry of Education and Research (BMBF) through the Software Campus Program.
References
[1] G. Singh, Akrigg, M. Di Maio, V. Fontana, Alitappeh. S. Khan, Saha, K. Jeddisaravi, F. Yousefi, J. Culley, al. Road: The road event awareness dataset for autonomous driving. IEEE transactions pattemn analysis and machine intelligence, (11)::1036-1544 2022.
[2] E. Giunchiglia, M. C. Stoian, S. Khan, F. Cuzzolin, and T. Lukasiewicz. Road-r: The au- tonomous driving dataset with logical requirements. Machine Learning, pages 1-31, 2023.
[3] S. Malla, C. Choi, I. Dwivedi, J. H. Choi, and J. Li. Drama: Joint risk localization and cap- tioning in driving- In Proceedings of the IEEF/CVF Winter Conference on Applications of Computer Vision, pages 1043-1052, 2023.
[4] E. Sachdeva, N. Agarwal, S. Chundi, S. Roelofs, J. Li, M. Kochenderfer, C. Choi, and B. Dar- iush. Rank2tell: A multimodal driving dataset for joint importance ranking and reasoning. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 7513-7522, 2024.
[5] B. Wilson, W. Qi, T. Agarwal, Lambert, J. Singh, S. Khandelwal, B. Pan, R. Kumar, A. Hart- nett, J. K. Pontes, D. Ramanan, P. Carr, and J. Hays. Argoverse 2: Next generation datasets for self-driving perception and forecasting. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks (NeurIPS Datasets and Benchmarks 2021), 2021.
[6] Kochakarn, D. De Martini, D. Omeiza, and L. Kunze. Explainable action prediction through self-supervision scene graphs. In 2023 IEEE International Conference Robotics and Automation (ICRA), pages 1479-1485. IEEE, 2023.
[7] D. Omeiza, S. Anjomshoae, H. Webb, M. Jirotka, and L. Kunze. From spoken thoughts to automated driving commentary: Predicting and explaining intelligent vehicles' actions. In 2022 IEEE Intelligent Vehicles Symposium (IV), pages 1040-1047. IEEE, 2022.
[8] R. Wickramarachchi, C. Henson, and A. Sheth. An evaluation of knowledge graph embeddings for autonomous driving data: Experience and practice. arXiv preprint arXiv:2003. 00344, 2020.
[9] A. Zareian, S. Karaman, and S.-F. Chang. Bridging knowledge graphs to generate scene graphs. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXIII 16, pages 603-623. Springer, 2020.
[10] V. Vovk, A. Gammerman, and G. Shafer. Algorithmic Learning in Random World. Springer- Verlag, Berlin, Heidelberg. 2005. ISBN 0387001522.
[11] G. Shafer and V. Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
[12] A. N. Angelopoulos and S. Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.07511, 2021.
[13] L. Gan, Y. Kim, J. W. Grizzle, J. M. Walls, A. Kim, R. M. Eustice, and M. Ghaffari. Multitask learning for scalable and dense multilayer bayesian map inference. IEEE Transactions on Robotics, 39(1)669--717, 2022.
[14] W. Zhou, Т. Gong. J. Lei, and Yu. Dbenet: Dynamic bilateral cross-fusion network for rgb-t urban understanding in intelligent vehicles. IEEE Transactions Systems, Man, and Cybernetics: Systems, 2023.

---

[15] K. Sirohi, S. Marvi, D. Büscher, and W. Burgard. Uncertainty aware panoptic segmentation. IEEE Robotics and Automation Letters, 8(5): 226662666,222,,22 2023.
[16] J. Sun, Y. Jiang J. Qiu, P. Nobel, M. J. Kochenderfer, and M. Schwager. Conformal pre- diction for uncertainty-awarr planning with diffusion dynamics model. Advances in Neural Information Processing Systems, 36, 2024.
[17] J. Lidard, H. Pham, A. Bachman, B. Boateng, and A. Majumdar. Risk-calibrated human-robot interaction via set-valued intent prediction. In ICRA 2024 Workshop { ('teetemdash) Back to the Future: Robot Learning Going Probabilistic.
[18] A. Z. Ren, A. Dixit, A. Bodrova, S. Singh, S. Tu, N. Brown, P. Xu, L. Takayama, F. Xia, J. Varley, et al. Robots that ask for help: Uncertainty alignment for large language model planners. In Conference on Robot Learning, pages 661-682. PMLR, 2023.
[19] Y. Zhang, S. Wang. Y. Zhang, and D. 7. Chen. Rr-ep: Reliable-region-based conformal predic- tion for trustworthy medical image classification. In International Workshop on Uncertainty for Safe Utilization of Machine Learning in Medical Imaging, pages 12-21. Springer, 2023.
[20] A. Fisch, T. Schuster, T. Jaakkola, and R. Barzilay. Few-shot conformal prediction with aux- iliary tasks. In International Conference on Machine Learning, pages 3329-3339. PMLR, 2021.
[21] J. Teng, C. Wen, D. Zhang, Y. Bengio, Y. Gao, and Y. Yuan. Predictive inference with feature conformal prediction. 11th International Conference on Learning Representations, ICLR 2023, 2023.
[22] L. Lindemann, M. Cleaveland, G. Shim, and G. J. Pappas. Safe planning in dynamic environ- ments using conformal prediction. IEEE Robotics and Automation Letters, 2023.
[23] A. Dixit, L. Lindemann, S. X. Wei, M. Cleaveland, G. J. Pappas, and J. W. Burdick. Adaptive conformal prediction for motion planning among dynamic agents. In Learning for Dynamics and Control Conference, pages 300-314. PMLR, 2023.
[24] P. Sun, H. Kretzschmar, X. Dotiwalla, A. Chouard, V. Patnaik, P. Tsui, J. Guo, Y. Zhou, Y. Chai, B. Caine, et al. Scalability in perception for autonomous driving: Waymo open dataset. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2446-2454, 2020.
[25] A. Fisch, T. Schuster, T. S. Jaakkola, and R. Barzilay. Efficient conformal prediction via cascaded inference with expanded admission. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021.
[26] T. Ding, A. Angelopoulos, S. Bates, M. Jordan, and R. J. Tibshirani. Class-conditional con- formal prediction with many classes. Advances in Neural Information Processing Systems, 36, 2024.
[27] M. Sadinle, J. Lei, and L.. Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223-2555 2019.
[28] Y. Romano, M. Sesia, and E. Candes. Classification with valid and adaptive coverage. Ad- vances in Neural Information Processing Systems, 33:3581-3591, 2020.
[29] A. N. Angelopoulos, S. Bates, M. I. Jordan, and J. Malik. Uncertainty sets for image classifiers using conformal prediction. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
[30] C. Russo, K. Madani, and A. M. Rinaldi. Knowledge acquisition and design using semantics and perception: case study for autonomous robots. Neural Processing Letters. 53(5):3153- 3 3668, 2021.
10

---

[31] B. Yu, H. Kasaei, and M. Cao. Co-navgpt: Multi-robot cooperative visual semantic navigation using large language models. arXiv preprint crXiv:2310.07933,, 2023.
[32] C. Tang, D. Huang, W. Ge, W. Liu, and H. Zhang. Graspgpt: Leveraging semantic knowl- edge from large language model for task-oriented grasping. IEEE Robotics and Automation Letters, 2023.
[33] Y. Feng, W. Hua, and Sun. Nle-dm: Natural-language explanations for decision making of autonomous driving based on semantic scene understanding. IEEE Transactions on Intelligent Transportation Systems, 2023.
[34] R. Michelmore, M. Wicker, L. Laurenti, L. Cardelli, Y. Gal, and M. Kwiatkowska. Uncertainty quantification with statistical guarantees in end-to-end autonomous driving control. 2020 IEEE international conference on robotics and automation (ICRA), pages 7344-7350, IEEE, 2020.
[35] N. Shah and S. Srivastava. Zero-shot option invention for robot planning under uncertainty. In CoRL 2023 Workshop on Learning Effective Abstractions for Planning (LEAP), 2023.
[36] X. Tang, K. Yang, H. Wang. J. Wu, Qin, W. Yu, and D. Cao. Prediction-uncertaintt-ye decision-making for autonomous vehicles. IEEE Transactions Intelligent Vehicles, 7(4): 849-862, 2022.
[37] X. He, W. Huang, and C. Lv. Toward trustworthy decision-making for autonomous vehicles: A robust reinforcement learning approach with safety guarantees. Engineering, 33:77-89, 2024.
[38] D. Fu, X. Li, L. Wen, M. Dou, P. Cai, B. Shi, and Y. Qiao. Drive like human: Rethinking autonomous driving with large language models. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 910-919, 2024.
[39] D. Shah, B. Osiński, S. Levine, al. Lm-nav: Robotic navigation with large pre-trained models of language, vision, and action. In Conference robot learning, pages 492-504. PMLR, 2023.
[40] Y. Yang, Q. Zhang, C., D. S. Marta, N. Batool, and Folkesson. Human-centric autonomous systems with Ilms for user command reasoning. In Proceedings of the IEEE/CVF Winter Conference Applications of Computer Vision, pages
2024.
[41] S. Wang, Z. Yu, X. Jiang, S. Lan, M. Shi, N. Chang, J. Kautz, Y. Li, and J. M. Alvarez. Om- nidrive: A holistic am-agent framework for autonomous driving with 3d perception, reasoning and planning. arXiv preprint arXiv:2405.01533 2024.
[42] J. F. Mullen Jr and D. Manocha. Towards robots that know when they need help: Affordance- based uncertainty for large language model planners, arXiv preprint 2rXiv:2403.13198, 2024.
[43] X. Guan, Liu, Lin, Lu, He, X. Han, and Sun. Mitigating large language model hallucinations via autonomous knowledge graph-based retrofitting, In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 18126-18134 2024.
[44] S. Schööbs, S. Pareek, J. Goncalves, and W. Johal. Robot-assisted decision-maaing Unveiling the role of uncertainty visualisation and embodiment. In Proceedings of the CHI Conference on Human Factors Computing Systems, pages 1-16, 2024.
[45] J. Lee, J. Feng, M. Humt, M. G. Müller, and R. Triebel. Trust your robots! predictive uncer- tainty estimation of neural networks with sparse gaussian processes. In Conference on Robot Learning, pages 1 1168-114 119. PMLR, 2022.
[46] I. Gibbs and E. Candes. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34: 34:1660-1672, 2021.
11

---

[47] R. Kaur, S. Jha, A. Roy. S. Park, E. Dobriban, O. Sokolsky, and I. Lee. idecode: In- In-distribution equivariance for conformal out-of-disstibutioo detection. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 36, pages 7104-7114, 2022.
[48] C. Tyagi and W. Guo. Multi-label classification under uncertainty: A tree-based conformal prediction approach. In Conformal and Probabilistic Prediction with Applications, pages 488- 512. PMLR, 2023.
[49] A. Derhacobian, J. Guibas, L. Li, and B. Namboothiry. Adaptive prediction sets with class conditional coverage.
[50] O. Dunn. Multiple comparisons among means. Journal of the American statistical associa- tion, 56(293):52-64) 1961.
[51] L. Mlodzian. Z. Sun, H. Berkemeyer, S. Monka, Z. Wang, S. Dietze, L. Halilaj. and J. Luet- tin. nuscenes knowledge graph-a comprehensive semantic representation traffic scenes for trajectory prediction. Proceedings of the IEEE/CVE International Conference on Computer Vision, pages 42-52, 2023.
[52] L. Halilaj. J. Luettin, C. Henson, and S. Monka. Knowledge graphs for automated driving. In 2022 IEEE Fifth International Conference on Artificial Intelligence and Knowledge Engineer- ing (AIKE), pages 98-105. IEEE, 2022.
[53] J. P. Queralta, J. Taipalmaa, B. C. Pullinen, V. K. Sarker, T. N. Gia, H. Tenhunen, M. Gab- bouj, J. Raitoharju, and T. Westerlund. Collaborative multi-robot search and rescue: Planning, coordination, perception, and active vision. leee Access, 8: 1961777111,6,,, 2020.
[54] F. Yazdani, S. Blumenthal, N. Huebel, A. K. Bozcuoğlu, M. Beetz, and H. Bruyninckx. Query- based integration of heterogeneous knowledge bases for search and rescue tasks. Robotics and Autonomous Systems, 1 117:80-91, 2019.
[55] H. Kwak, J. Lee, J. J. Whang, and S. Jo. Semantic grasping via knowledge graph of robotic manipulation: graph representation learning approach. IEEE Robotics and Automation Let- ters, 7(4):9397-9404, 2022.
[56] M. Hanheide, Göbelbecker, Horn, A. Pronobis, K. Sjöö, A. Aydemir, Jensfelt, C. Gretton, Dearden, M. Janicek, et al. Robot task planning and explanation in open and uncertain worlds. Artificial Intelligence, 247:1 2017.
[57] M. Hanheide, C. Gretton, R. W. Dearden, N. A. Hawes, J. L. Wyatt, A. Pronobis, A. Aydemir, M. Göbelbecker, and H. Zender. Exploiting probabilistic knowledge under uncertain sensing for efficient robot behaviour. In Twenty-Second International Joint Conference on Artificial Intelligence, 2011. 1.
12

---

Supplementary Material for the Paper
Conformal Prediction for Semantically Aware Autonomous Perception in Urban Environments
Proofs
13
A.1 Background For Proofs: Cascaded Conformal Prediction
13
A.2 Proof of Theorem 3.1
14
A.3 Proof of Corollary 3.1
15
A.4 Details About the Correction Procedure
16
Structure of the Knowledge Graph
16
B.1 Complete Structure of the Knowledge Graph
17
B.2 Impact of the Knowledge Graph Size on KRPS
17
C Results for Further Task Sequences
20
D Qualitative Results
20
D.I Qualitative Results on the ROAD Dataset
21
D.2 Qualitative Results on the Waymo/ROAD+++ Dataset
Further Details About Empty Prediction Sets
More on the Practicality of KRPS
25
A Proofs
A.1 Background For Proofs: Cascaded Conformal Prediction
Cascaded conformal prediction (cascaded-CP) [25] technique that allows to prune prediction sets sequentially for a single task, using cascade of different non-conformity scores over m steps. Since different statistical tests are applied to the data set, the multiple hypothesis testing (MHT) problem arises, which leads to an increased family-wise error rate (i.e., false positives), making the CP procedure invalid. Cascaded-CP makes use of p-value correction procedures M, such as Simes corrections, to account for MHT problem. Cascaded-CP is formalized in Theorem A.I.
Theorem A.1 (Cascaded-CPP [25]) For any sequence of non-conformity measures (S1, ..., Sm). which yields p-values (P,,.., Pn) and E [0,1], 1), the prediction set C5 (Xtest) step j m is defined as:
(Xtet)) = EY (x
(6)
where Py is the corrected p-values using the procedure M for candidate at step j. Then Vj e m), (Xtest) satisfies Equation 1, and (m (Xtest) S C (Xrest).
13

---

In this work, we show that Theorem A.1 can be extended to cover multiple tasks in cascade. Fur- thermore, in our case the tasks are not required to share the same lahel space. By constructing a knowledge graph facilitating semantic mapping between tasks, our approach accommodates differ- ent tasks. Notably, Cascaded-CP can be seen as a sub-case of our work if all tasks are identical.
A.2 Proof of Theorem 3.1
We consider tasks Te and Ti that performed sequentially. Our goal is to prove that the pre- diction set CKRPS obtained by performing any CP procedure the set CP,, which represents the semantic mapping Me-i of the set CKRrs, satisfies 2 properties: marginal coverage, and semantic consistency with respect to C RPS and K.
Marginal Coverage
First, we prove the marginal coverage property of the set CKRPS, that is: Ply
C CKRPS (Xtest) 2
The set C CKRPS constructed using a CP procedure, meaning that it satisfies Equation 1, and we have:
Ply test C (Xtest)) CXRPP((XEst) 2 21-a
(8)
The semantic mapping Ma is deterministic mapping that assigns of possible locations to each element of (Xtees((tee)))). Knowing that the true value of the subsequent task Y is the image of the true value of the starting task Y the resulting mapping set CK (Xtest) = Mc-K (Xtes)) contains the Ylest with a probability that is at least equal to 1 a, as expressed in Equation 9.
Plytess (Xteat)] 2 1-a
(9)
From the CP coverage Theorem 2.1, we can conclude the existence of a p-value P that satisfies: PlYtest E (Xtest)
a = Pppp a) Sa
(10)
At this step, we have two distinct p-values for the subsequent task Ti, namely P/C and P.. The p-value P. is employed in the construction of the set CK whereas Pt is utilized for forming the set ("test)). representing the CP-based set for task Ti independently of the knowledge provided by the prior task Te, established on C.K RPS
Subsequently, we execute a cascaded- procedure using Theorem A. on the p-values Pt, PK. We incorporate a p-value correction procedure denoted as M, resulting in corrected p-values Pt, P... and we have:
Plytest E (Xteet) n c (Xreet) 2
+ P|Y E C RPS (PPRRRS(Xeaa (Xreet) 2 a
which is the result stated in Equation 3.
Semantic Consistency Our goal now is to show that the newly constructed prediction set CKK RPS semantically consistent with respect to C CKRPS and K. This result of semantic consistency comes from the fact that for each element Y C.K C,KPP we have y' E C² (Xtest) n Mo-. (C (Xtsst)))) which gives the semantic consistency property.
meaning that C C (M
further refine the prediction sets generated by any CP procedure given K. and a related task, by removing classes that are not semantically consistent with other tasks, without losing the property of marginal cov- erage, provided that the p-values are properly corrected. The semantic refinement in KRPS plays an additional role in highlighting corner cases. In urban applications, is typical to start with a basic knowledge graph and incrementally add new class relationships as data becomes available. This process, however, may encounter corner cases or semantic inconsistencies, like vehicles on sidewalks, not covered by the knowledge graph. KRPS addresses these instances by outputting an empty prediction set when semantically consistent vehicle position cannot be found. This empty
Implications of Theorem 3.1 The direct implication of Theorem 3.1 is that
14

---

Transitive Conditional Semantic Consistency
Agent C CRRPS RPS
Locations CkRPS
Actions CRPS
Conditional Semantic Consistency
Conditional Semantic Consistency
Figure 3: Implications of Theorem 3.1 (blue) and Corollary 3.1 (green) the semantic consistency.
set signals potential knowledge graph gaps or corner cases, prompting further investigation by end- users. Updating the knowledge graph and performing a calibration step is sufficient to adapt to new data without retraining the model.
A.3 Proof of Corollary 3.1
The sets CKRPS, CKRPS and, C-KPPS are prediction sets constructed using KRPS, in the de- scribed order. Given this, our goal to prove that C RPS semantically consistent with respect C CKRPS and K. Since C CKRPS constructed based on Theorem 3.1, we have CKRPS is seman- tically consistent with respect to CKRPS and IC, i.e.,
VY, E CKRPS 3Y CKRPS /Ya E Mi)a(Yi)
(1I)
Since CKRPS is constructed using KRPS based on Theorem 3.1, C CKRPS semantically consistent with respect to C.K CKRPS and IC and we have:
VY E C CKRPS BY, E CKRPS Yi Mo-i((Y)
(12)
Based on Equations and 12, we can establish that:
VY, CKRPS JY, C.RPPSYY Mo
(13)
Which gives that CKP semantically consistent with respect to CRRP and K.
Implications of Corollary 3.1 Corollary 3.1 establishes the transitive properties of semantic con- sistency, defined using Definition 3.1. As depicted in Figure 3, this result implies that two pre- diction sets from sequential tasks maintain semantic consistency, as long as they are built in sequence relative to shared task in the middle. This finding holds sig- nificance as knowledge bases evolve over time with the inclusion of new tasks. Employing KRPS ensures guarantees of semantic consistency with all prior tasks, by uniquely verifying semantic con- sistency for the latest executed task.
if constructed independently,
Comments on the Coverage Guarantees of KRPS. The coverage guarantee, as currently framed in Theorem 3.1, holds in expectation over the calibration sets, reflecting the standard practice in conformal prediction ensure broad applicability and robustness across various operational scenar- ios [29]. KRPS prioritizes generalizability and statistical validity across diverse conditions, which is why the guarantee is designed to hold in expectation rather than conditionally. However, KRPS can be easily adapted to conditional coverage guarantees by adopting class conditional calibration procedures, such as in [49].
Comments on the Semantic Consistency Guarantees of KRPS. KRPS guarantees conditional semantic consistency on the prediction sets of the subsequent tasks relative to the first task and the knowledge graph. This means that while KRPS ensures that the are semantically consistent given the output of the first task and according to the relationships defined in the knowledge graph, this consistency is conditional those of initial outputs of the first task executed.
15

---

A.4 Details About the Correction Procedure
In our implementation of KRPS, addressing the challenges of multiple hypothesis testing is crucial due to the simultancous considcration of multiple semantic categories in the knowledge graph. To ensure the validity our statistical inferences while managing the family-wise error rate (FWER), we employ the Bonferroni correction procedure. The Bonferroni procedure [50] is conservative approach that adjusts for multiple comparisons by dividing the desired significance level by the number of hypotheses tested,
Specifically, individual tests are conducted at a significance level a, the Bonferroni correction modifies the significance threshold for each test to & For KRPS, where each agent's classification m. can lead multiple related hypotheses about actions and locations, the correction ensures that the
overall probability of making one or more type errors does not exceed
Mathematically, this is represented as:
Ordjjsted
Where is the total number of hypotheses, which corresponds to the number of potential action and location classifications linked to each agent class. By applying the adjustment for the values of a, KRPS maintains the control over the error rates across all tests.
B Structure of the Knowledge Graph
In the following, provide more details about the knowledge graph used to model the semantic relationships between the entities in the urban environment. We adopt simple, yet effective on- tological model based on the following semantic relationship: Agent performs action in location. It is possible to adopt different task orders, e.g., Action is performed in location by agent. In our setup, the classification of an agent, its location, and its action, correspond to different tasks, that are performed by separate models or separate heads of single model. This ensure that we consider a multitask setup, contrast to situations where a model outputs a triplet, which we consider case of multi-class classification tasks.
We adopt the class labels provided by the ROAD and the Waymo/ROAD++ datasets [1, 24] for all the tasks that we consider. For Completeness, we report the list of agent, location, and action classes, as they are described in the ROAD dataset, in Table 2, Table 3. and Table 4, respectively.
Based on the class labels for each task, the semantic mapping functions MT:+TA= where T₃ and T represent the start and the subsequent tasks, respectively, are constructed through the examination of possible label assignments between the tasks in the training set.
More in details, the construction of the knowledge graph begins by loading semantically coher- ent triplets from ground truth labels in the training set, which define relationships between agents, actions, and locations. Each agent class is mapped to corresponding action and location classes through boolean arrays within structured dictionary. The construction procedure ensures also that the reverse mappings can be queried, in case different sequence task is considered. The knowledge graph construction procedure is detailed in Algorithm 2.
In the KRPS framework, the ground truth data is utilized not merely as examples for training models but also as a fundamental component for constructing the knowledge graph. This dual utilization allows the ground truth data to both train the predictive model and guide the development of semanti- cally aware prediction sets using KRPS, afterwards, ensuring that the prediction sets are statistically valid and semantically consistent across the tasks. Under the assumption of data exchangeability, central tenet of conformal prediction, we assume that the data in the training, calibration, and test sets come from the same distribution. This assumption helps limit the incompleteness of the knowl- edge graph construction procedure. Even the knowledge from the training set is incomplete, KRPS
Waaymo/ROAD+H https: htaps://sites... ht/s:/siiss.ggglllleeesss wwtpw//wwwwwwwwwe/e/ee.eeee plus/dataset
16

---

manages this by outputting empty sets, prompting the user to address gaps in the knowledge graph or to identify potential anomalies from out-of-distribution samples.
is important acknowledge that the construction of knowledge graphs can be approached through various methodologies beyond the one implemented KRPS. The method described herein was selected for its simplicity and effectiveness within application scope. Alternative methods, such as [51, 52], demonstrate the capacity to construct complex knowledge graphs tailored to autonomous driving scenarios using different types of input data and for various tasks, such as perception and navigation. Such versatility not only illustrates the scalability of knowledge graph construction processes but also supports their adaptability across different semantic dimensions.
Algorithm 2: Construction of the Knowledge Graph
Input Grooun truth annotations containing agent, action, and location classes from training set.
Output: K:: A dictionary representing the knowledge graph where agent classes are linked to semantically coherent actions and locations.
1: procedure WOW.LDKNOWWEDGEEGE
2: Load ground truth labels from GT
3: Extract semantically coherent triplets of agents, actions, and locations
4: Initialize an empty dictionary for the knowledge graph
5:
For each agent class:
6:
Create a sub-dictions dio-iiciionary for actions and locations
7:
Initialize boolean arrays for actions and locations based on class counts Populate the boolean arrays using triplet data: For each triplet:
8:
9:
10:
Mark the corresponding action and location semantically coherent Return the constructed knowledge graph, K.
12:
end procedure
B.1 Complete Structure of the Knowledge Graph
In the following. detail the finalized knowledge graph utilized in our implementation. Table summarizes the semantic mappings Me-r and Me-s1- The semantic mappings Ma and Ma-s! are represented in Table 6. Finally, the semantic mappings Mi and Mi are represented in Table
B.2 Impact of the Knowledge Graph Size on KRPS
In this section, we systematically evaluate the influence of knowledge graph completeness on the performance of KRPS. Motivated by the necessity to ascertain how the granularity and extent of semantic data affect predictive outcomes, the completeness of the knowledge graph varied at
Label Name
Abbreviation
Car
Car
Medium Vehicle
MedVeh
Large Vehicle
LarVeh
Bus
Bus
Motorbike
Mobike
Emergency Vehicle
Em Veh
Pedestrian
Ped
Cyclist
Cyc
Vehicle Traffic Light
TL
Other Traffic Light
OthTL
Table 2: List of agent classes and their abbreviations as reported in the ROAD dataset [1].
17

---

Label
Abbreviation
In vehicle lane In outgoing lane In incoming lane
VehLane
OutgoLane
Incoml Lane
In outgoing cycle lane In incoming cycle lane
OutgoCyclaane
IncomCycLane
On left pavement
LftPav
On right pavement
RhtPav
On pavement
Pav
At junction
Jun
At crossing
Xing
At bus stop
BusStop
At parking
parking
Table 3: List of used location classes and their abbreviations reported in the ROAD dataset [1].
Label
Abbreviation
Moving away
Mov
Moving towards
MovTow
Moving
Mov
Braking
Brake
Stopped
Stop
Indicating left
IncatLft
Indicating right
IncatRht
Hazard lights
HazLit
Turning left
Turn
Turning right
TurnRht
Moving right
MovRht
Moving left
MovL.t
Overtaking
Ovtak
Waiting cross
Wait2X
Crossing road from left Crossing road from right
XingFmLft
XingFmRht
Crossing
Xing
Pushing object Traffic light red Traffic light amber
PushObj
Red
Amber
Traffic light green
Green
Table 4: List of used action classes and their abbreviations as reported the ROAD dataset [1]
Actions
Locations
Mov:Awayy May Low, Stop, WaiiXXXinng f mihhi.
VehLine, Ltt.a.a.........hhhaaaaaa
BusSiup
Mon:Away Moviow Brake Stop, locati Incatthrr TtrL
VehLane: Outt-Oonooona ane IncomLanee Jun
Cye
MovAwway Moy Stop T.
XingFillf
Vell anc. Outgol ane one ane EnclmCycl.aee
Mobike
Mor Ausay MovTow Banke Stop, Ircad fiIncaRRhr,Tt Twrl T.Ththhr
anc Outgol ane anc Jne.Ion
MedNNh
Mox Tow, Stop. TurRhi TurLit. Drake
Invomblnne Jun Jun.OuigoLane
Larveh
Mov Stogs XingFmll.
Brake
InsomLane. Jaw..aoon......oo...om
Vehl fncoml Jun, RusStop
Table 5: The semantic mappings between the agent classes and the action classes (Ma-sa), and the
agent classes and the location classes (Ma--i).
18

---

Action
List Agents
List of Locations
MovAway
Car Me.Vehh Med.ee LarVeh
VehLanc Outgolotgooannccc Satggooannn.Onooyyyyeo www. www.
MovTow
Vene.ane Incoml ane www.lnnooCyllaannc htt.ee/.ffP.,hPPParaaaa
Mov
Pod
Pav
Brake
Car
JeneLaneJJun
Stup
MedlCanCyc,MeaaeebBBuuu
VehLane Incoml L hnw.oo/aa...neommmyylllllll htw.://w...attttta.aaooooaooeeee
IncatLn
Car
VehLane
IncatRhr
Car
IncomLance Jnn
TurLf
CanCye
Veh
TurRht
CarMedVeh
IncomLanc.Jum
Car
VehLLane
Wair2X
Ped
LAPax,RhiPav
XingFmLL
Cyre
VehLane Lncommlneeeeeeeeeeemommmm Jun.xinnnnn
Xinh
Ped
Vehl.ane, Incoml Incloon ane RhiPav,,un
Xing
Ped.Cye
Xing
PushObi
Pod
LitPav.RhtPav
Table 6: The semantic mappings between the action classes and the agent classes (Ma-sa), and the
agent classes and location classes (Ma-i)..
Location
List of Agents
List of Actions
Nehl lane
Ped,Can.Cy..iis
Mov NooeAway,Mor Morkeoo.Brakkeeene Stop.
Incal it, Stop.fent
Turl ft, Pin fi, Fing
OutgoLanc
CarCyy
OytgoCycLLame
Cyc
MovAway
Incoml aane
Cye, MeeCCarryyeMeeiVee..HB. Bus
Mor Stwp Snt.ponn.aRttititt..... Turkht, Tingei Ping
LyennC
MorTow,
Pav
Ped
MovAway,
MowAwayyMMv.Soy Mov.Stop
LitPav
Pyd,Cyc
MovAway, MovAAway.Mor/ii MorTow,Stop Wair2X, PushOhj
RhdPav
Ped
MovAway, Mor WaitXX, XingFiiiiiiittccccc.m.. PustiP PashiOoi
Jan
MovAway, Mov Brake, https:/w...............t..ttttte
xing
Ped
Xingfmmift
RosStop
Ped,
Stop
parking
Car
parking
Table 7: The semantic mappings between the location classes and the agent classes (Micc), and
the location classes and action classes (M)++.
50%, 70%, and 90% of its full capacity. The Results in Table 8 report the results the ROAD dataset with = 0.1 for the (agent - location] sequence, using the "1 - softmaz" score with KRPS. The results reveal a decrease in semantic consistency corresponding with reduced knowledge graph completeness, although statistical coverage guarantees are maintained. Furthermore the set size larger with reduced portions of the knowledge graph. This result is expected, as the removed connections from the reduced knowledge graph cannot used during the refinement process, which impacts the set size and the semantic consistency while semantic consistency decreases, Theorem 3.1 and Corollary 3.1 remain valid. This is because these theorems are formulated with respect to the currently used portion of the knowledge graph; therefore, semantic consistency remains perfect (value of 1) when considered within the context of the available graph segment.
to the full graph. It's important to note that
Metrics
% of used knowledge graph
50%
70%
90%
100%
DTC
0.07
0.06
0.05
0.02
SS
6.82
6.53
5.96
5,86
SC full K)
0.83
0.86
0.98
1.00
SC (w.it reduced K)
1.00
1.00
1.00
1.00
Table 8: Effects of the knowledge graph size on the performance of KRPS. We evaluate the per- formance of KRPS with different sizes of the knowledge graph (50%, 70%, 90%) and compare it to the reference of 100% of the knowledge graph (designated in Bold in the table). The results are obtained for 0.1 for the (agent location) sequence, using the "1 softmax" score with KRPS.
19

---

Task
Score
Method
S8
a
DTC
0.1
SC
SS
a =
DTC
0.2
SC
SS
a 0.3
DTC
SC
a D.4
DTC
SC
5S
D. 15.5
DTC
SC
Location
APS
Stand
KRPS
5,90
7.12
0.05
0.02
0.80
1,00
6.07
4.96
0.10
0.05
0.79
1.00
5.38
4.05
0.01
0.69
1.00
3.65
0.20
0.12
1,00
0.76
4.20
2.61
0.27
0.00
1.00
RAPS
Stand
KRPS
2.18
2.66
0.07
0.05
0.89
1,00
2.03
1,78
0.15
0.13
1,00
0.93
1.58
1.70
0.25
0.14
0.95
1.00
1.45
1.56
0.34
0.13
1.00
0.96
1.46
1.36
0.43
0.22
1.00
0.95
APS
Stand
KRPS
9.77
0.05
0.75
8.01
0.10
0.73
8.14
5.59
0.30
0.72
5.72
0.30
0.70
6.56
0.14
0.00
0.09
Action
RAPS
KRPS
Stad
3.82
4.57
0107
0.03
0.84
1.00
3.26
3.54
0.13
0.02
0.87
1,00
3.27
1.39
0.23
0.13
0.56
1.00
2.54
2.22
0.25
0.15
1.00
0.92
2,52
2.55
0.37
0.17
0.9T
1.00
Table 9: Results on the ROAD dataset for the task sequences {agent - location] and {agent action).
Tisk
Score
Method
88
DTC
01.1
SC
DTC
0.22
SC
DTC
0.3
8S
DTC
0.4
SC
SS
DTC
D.5
SC
Stand
9.02
0.07
0.79
7.92
0.10
0.76
3.97
0.18
0.73
4.03
0.22
0.71
3.98
0.29
0.64
Location
APS
KRPS
7.50
0.01
1.00
5.99
0.06
1.00
4,00
0.01
1,00
3.24
0.14
1.00
2.73
0.05
1.00
RAPS
Stand
KRPS
2.01
0.04
0.87
1,00
2.04
0.10
1.00
1.35
0.23
0.14
1.00
1.17
1.83
0.34
0.09
1.00
1.10
1.40
0.09
0.95
1.00
Stand
10.41
0.05
0.77
6.84
0.13
0.74
6.02
0.15
0.34
5.36
0.12
0.78
4.8
0.20
0.68
Action
KRPS
5.98
0.02
1,00
4.18
0.02
1.00
3,90
0.07
1.00
3,87
0.12
1,00
3.94
0.08
1.00
RAPS
Stand
4.36
0.06
0.87
3.03
0.15
0.89
2.48
0.16
0.86
1.50
0.24
0.94
1.20
0.37
0.90
1.00
1.07
0.07
1.02
Table 10: Results on the Waymo/ROAD++ dataset for the task sequences fagent + location] } and
fagent action).
C Results for Further Task Sequences
In Section 4.5, reported results for sequences of tasks: {agent - location] and (agent - action} for a 00.1, 0.2, 0.4]. In the following, we present more results both datasets for the full set of values of a 10.1, 0.2, 0.3, 0.4, 0.5) for the sequences fagent + location) and {agent + action} in Table 9 and Table 10, respectively. Furthermore, we present results using sequences of tasks on the ROAD dataset to show the capability of KRPS to handle sequences with higher numbers of tasks and in different task orders. The 3-tasks sequences that we consider are: Segl {agent + action - location), and Seq2 flocation > action > agent). We use the same evaluation set-up and data splits reported in the evaluation section in our paper. The results reported in Table1 and Table 12, respectively.
In all task sequences, KRPS still holds the theoretical coverage guarantees for all values of a. More importantly, KRPS achieves the desired coverage rates while being able to reduce the set size con- siderably. The conditional semantic consistency also holds, as guaranteed by Theorem 3.1 and Corollary 3.1. For all task sequences, the conditional semantic consistency for task 2 with respect to task and K,, task 3 with respect task 2 and K., and task 3 with respect to task 1 and K,, is 100%.
D Qualitative Results
In this section, present further qualitative results on the ROAD and Waymo/ROAD++ datass datasets for the task sequences {agent - action), {agent + location), and {agent + action - location). }.
Task
Score
SS
DTC
SC
SS
DTC
0.2
SC
SS
DTC
SC
DTC
SC
SS
DTC
0.5
SC
APS
KRPS
Stand
9.82
0.05
0.71
8.14
5.84
0.10
0.02
0.65
6.91
4.79
0.15
0.61
3.37
0.21
0.58
1.00
5.10
0.26
0.56
Action
RAPS
Stand
KRPS
4.73
3.84
0.07
0.06
0.84
1.00
3.98
3.26
0.13
0.12
0.87
1.00
1.16
2.65
0.13
0.17
1.00
0.9
2.61
2.24
0.26
0.15
0.92
1.00
2.20
1.93
0.33
0.21
0.3
1.00
APS
Stand
KRPS
7.67
6.33
0.05
0.01
0.83
1.00
5.30
6.77
0.14
01.00
0.82
1.00
6.19
4.53
0.21
0.08
0.50
1.00
5.80
3.86
0.22
0.00
0.78
1.00
5.31
3.23
0.24
0.01
0.77
1.00
Location
RAPS
KRPS
2.06
0.07
1.00
2.38
2.12
0.16
1.00
1.80
0.04
0.95
1,00
1.69
0.13
0.96
1.00
1.57
0.13
1.00
Table 11: Results on the ROAD dataset for the task sequence {agent -> action + locaaiio]..
20

---

Task
Score
Method
SS
a= D.1
DTC
SC
58
a 0.2
DTC
SC
55
a:
DTC
SC
SS
a 0.1
DTC
SC
55
a 0.5
DTC
SC
APS
Stand
0.05
0.72
8.15
0.00
0.64
0.21
0.60
0.20
Action
RAPS
Stand
KRPS
7.35
4.73
0.07
0.00
0.82
1.00
6.02
3.98
0.15
0.00
0.85
1.00
3.16
4.91
0.20
0.00
0.89
1.00
3.97
0.26
0.00
0.91
1.00
2.20
3.20
0.35
0.01
1,00
0.92
KRPS
3.86
0.06
1.00
3,24
0.13
1.00
2.64
0.18
1,00
2.23
0.25
1,00
1.93
0.32
1,00
APS
Stand
7.00
0.06
0.53
6.52
0.13
0.54
6.16
0.20
0.55
5.76
0.27
0.56
5.48
0.33
0.55
KRPS
Agent
RAPS
KRPS
Stand
1.31
1.35
0.08
0.08
0.92
1.00
1.31
1,19
0.08
0.10
0.92
1.00
1.14
1.22
0:27
0.17
0.37
1,00
1.11
1.16
0.27
0.27
0.57
1.00
1,08
1.13
0.26
0.26
0.55
1,00
Table 12: Results on the ROAD dataset for the task sequence {location action agent).
D.1
Qualitative Results on the ROAD Dataset
Figure 4 shows 3 different scenes from the ROAD dataset with the agent of interest highlighted with the red bounding box. For each bounding box, we perform the indicated CP procedure to acquire the prediction sets for the agent classification task. Based on the agent prediction sets, we report the generated prediction sets with and without KRPS using the Softmax, APS, and RAPS scores.
Figure 6a shows a scene with and location classification tasks demonstrate how KRPS achieved substantial reduction for the prediction sets. This reduction is particularly observable for the location task with the softmax and APS scores, where the prediction set size is reduced by 4 classes.
stopping in the outgoing lane. The prediction sets for the action
Figure 4b shows scene with a bus stopping in the vehicle lane. All approaches succeed in in- cluding the correct labels in the prediction sets. The combination of KRPS with RAPS succeeds in constructing singleton for the tasks location and action classification. By applying KRPS, the action and location classes that are not relevant to the agent class are removed.
Figure 6b showcases scene with a bus moving towards in the incoming lane. Using KRPS, the size of the prediction sets for the action classification is reduced by 50% for the softmax score, by 75% for APS, and by 66% for RAPS. For the location classification task, KRPS reduced the prediction set size by 50% for the softmax score, by 50% for APS. For RAPS, the prediction set is not reduced, since both locations, incoming lane and junction are possible, given the agent class and its action.
The figures highlight the capability of KRPS to reduce the set size by removing action and location classes that are not relevant to the agent. Theorem 3.1 ensures that this removal procedure does not affect the marginal coverage property.
21

---

Agentiol:
Action/A:: [SSop'' lecatRhhe]
Location(7]: l'Icomlane" 'Outgolane" IncomCyclane' 'parking' "OutgoCyclane]
Agentiol: ['Car
Refined Action/4): ('Stop' Incatlef Brake Incatthhe)
Location I'Incomlane" 'Outgolane" 'Jun']
'Bux"] 'uzLit' 'MovAway]] Location!7]: I'IncomLana' "Outgolane" 'RiaPev' IscomCycLame' "parking" "OutgsCycLLane]]
"MeVVah'
Action)8): [Stop' TIccatit'
Refined 'Soop' "Iccatit" "Brake" MoxAwayy
MMdVVah' "EmVahh "LarVahi 'Bux']
Refined
Refined Location I'Incomaane' 'Outgolans" 'Jun']
RAPS
Agentt1::Caa
Action/2): [SStop' TheatLit)
Location(4]: I'Incomaane' "Outgolane" 'RasPev']
Agensi1): ['Car']
Refined Actioni2): ('Stop' TheasLit]
Refined Locationi3l: l'IncomLane 'OutgoLane" 'Jun'
(a) Scene of a car stopping the outgoing lane from the ROAD dataset [1] with prediction sets using 3 scoring functions for CP (Softmax, APS, RAPS) without and with KRPS.
Boftmax
Agentiäl: ['Bus' 'MedVill' 'LaVWah' 'Cye' 'Mobika' "EmiVal" 'TL' "OeNTL']
Action(77: (MMoAway' 'Stop' 'Bakee'
"Incathhe" 'InaaLift Amber]]
Locationt2]: ['Vehland' "OutgoCycLane"'
Agentiäl: l'Bus' 'MadViah'' 'LarWeh' "Cye' "Mobike" "EmiVah" 'TL' "OeNTL"]
Refined Action(2:: [MouAway' 'Stop']
Refined Lecation|2]: l'Vahlane' "DutsCCyeLame]]
Agential: l'Bus' 'MedVehl' "LaVeeh' "Oye' 'EniVel' 'TL' "OeNTL'
Action/S): (MowAway 'Brake" "IncatRht" Amber Ovvtak)
LocationiZl: l'Vehlaaee "OutgoCycLane"
Agenttal: l'Bus' 'MedVall' 'LarVeh'' "Cye' "Mobike" "EniVeh' 'TL' "OONTL]
Refined Action/221 "MovAway 'Stop]
Refined LocationIZI: ('VehLanee "DutgSCyeLane]]
Agenti 1:]
EMMwAway'
"HazLit)
Locationt11: ['Vehlane']
Agentin): l'Bur)
Action(1): [SStop]]
Refined Locationi ['eehLanee
(b) Scene of bus stopping in the vehicle lone from the ROAD dataset [1] with prediction sets using 3 scoring functions for CP (Softmax, APS, RAPS) without and with KRPS.
Softmax
Agentt7]: ('Bus' 'LarVeh'' 'EnVeh' 'MedVel' 'TL' "Pedf 'OthTL')
Astion/10): [MMvTow' 'Incatift' 'top'' InoazRhe' 'TurLit' 'HaLltt "Ovtak' "TurAtt 'XingFmLI'' [XingFmühe]]
Locadion(8l: ('Inoomaaee UJnn 'IncomyyoLane 'Outgolane' parrknng" "OutgoCyoLane" 'Vehlane" (BuSStop]]
KRPS:
Agenti77: I'Bus' 'LarVihh "EmVah"' 'MedVah 'TL "Ped (thTT:
Refined Action/S): ('Mooooo' 'Stop' TurRht' XingFmLit "XinFmRhht]
Refined Location14): ''IncomLane" 'Jun' 'VehLane' BusStop')
APS
Agent|7]: ('Bus" 'LarVeh' 'EmVahh' "MedVeh 'TL "Ped 'OthTL']
Action/10): [MovTow' 'Incatift 'top'' Incatithe" 'TurLit' 'HoLii' Ovtal' 'Turlthe 'Xingfmift XingFmlthe]
Location(a]: [incomLane' 'IncomCyclane' OOttolaane' pparking' "OungCCydaane VVellane 'BunStop')
Agenti27: l'Bus' 'LayVeh' "EmVehh' 'MedVeh 'TL "Ped 'thTT!)
Refined Action MovTow 'Stop' "Tufhhi" Xingfmift 'Xinffiltht" WWiiX]]
Refined Location]4]; 4): ('IncomLane" "Jue' 'Vahlane' BusStopp)
Agant| Buuu))
Action/80: ('MoTTow' 'IecsLit' 'Stog' "IncatRive' 'TurLit' "Mazit]]
Location121: ('IncomLane' UJnn']
Agent(11: ['Bux]]
Refined Action (Moo 'Stop']
Refined Location) ('IncomLane' 'Jun']
(c) Scene of bus moving towards in the incoming lane from the ROAD datasel [1] with prediction sets using 3 scoring functions for CP (Softmax, APS, RAPS) without and with KRPS.
Figure 4: Scenes from the ROAD dataset [1] with prediction sets using 3 scoring functions for CP (Softmax, APS, RAPS) without and with KRPS.
22

---

D.2 Qualitative Results on the Waymo/ROAD++ Dataset
Figure shows 2 different scenes from the Waymo/ROAD++ dataset, characterized by challenging situational and environmental conditions that may induce high uncertainty. The agent of interest is highlighted with the red bounding box. We perform the indicated CP procedure for each bounding box to acquire the prediction sets for the agent classification task. Based on the agent prediction sets, we report the generated prediction sets with and without KRPS using the Softmax, APS, and RAPS scores.
Figure 5a depicts low-light scenario where a pedestrian crosses the street with car in the back- ground of the bounding box. The challenging lighting conditions and complex scene composition contribute to uncertainty, prompting the model to assign vehicle-associated actions and locations such as Brake and outgoing lane. using KRPS mitigates this confusion by restricting the subsequent tasks to consider only classes suitable for pedestrians or bicycles, as determined by the agent classi- fication model. KRPS notably reduces uncertainty and shrinks the prediction set size by 80%, 83%, and 50% for softmax, APS, and RAPS predictions, respectively, for the action classification task. For location classification, the prediction set size is reduced by 50%, 75%, and 50% for softmax, APS, and RAPS, respectively.
Figure 5b illustrates scenario where a pedestrian is crossing the street while pushing bicycle. This presence of the bicycle often misleads models for action and location to assign characteristics typical of bicyclists, such as Brake and outgoing lane. KRPS addresses this issue by ensuring that only classes suitable for either pedestrians or bicycles are considered, as dictated by the initial agent classification results. This application of KRPS significantly reduces uncertainty and narrows the prediction set size by 71%, 60%, and 66% for the softmax, APS, and RAPS predictions for the action classification task, respectively. Similarly, for the location classification task, the prediction set sizes are reduced by 66%, 50%, and 66% for softmax, APS, and RAPS, respectively.
E Further Details About Empty Prediction Sets
In the KRPS framework, the occurrence of empty prediction sets critical aspect, designed to signal either anomalies in the detection or significant mismatches and gaps within the knowledge graph. The empty sets arise when no available classes meet the semantie and statistical criteria estab- lished by the knowledge graph and conformal prediction rules. In traditional conformal prediction, an empty prediction set is generated when the non-conformity score for any potential prediction ex- ceeds the calibrated threshold, indicating that none of the possible outcomes is statistically plausible within the given confidence level. KRPS enhances the traditional conformal prediction model by integrating a semantic layer that evaluates the coherence of potential predictions with the knowl- edge graph. This integration means that even if prediction is statistically plausible, it might still be rejected if it fails to align semantically with the knowledge graph. Hence, empty prediction sets may also occur due to the absence of semantically consistent labels, particularly in scenarios where the knowledge graph does not fully cover all possible real-world variations.
We conduct an experiment to quantify the frequency of empty prediction sets produced by KRPS and compare these outcomes to traditional conformal prediction baselines, to assess the impact of semantic layer in KRPS on the generation of empty sets. The results, depicted in Figure 6, show trend where - Softmar, APS, and their combination with KRPS produce more empty sets the value of a increases, a behavior expected as higher values lead conformal prediction approaches to generate smaller prediction sets, as they tolerate more risk. This is however different for RAPS, where the percentage of empty sets is zero across the different values of a. This is an expected be- havior since the regularization term in RAPS encourages the inclusion of additional labels if the set too small, thus preventing it from being empty. By adaptively adjusting the threshold for inclusion based on the desired coverage level, RAPS ensures that there is always at least one label that meets the criteria, thereby avoiding empty prediction sets. KRPS, in contrast to the baselines, consistently shows a higher frequency of empty sets due to the semantic consistency checks integrated. If po-
23

---

Softmax
Agemtzz:: 'Ped')
Action(S): Brake" 'TurLft; 'Stop' Dincathhh, (XingFmiit)
Location(@x 'incLane' ManggolaneeJJnii "BusStop)
KRPS
AgentiZ):[Cye: 'Ped')
Refined Action|t); "XingFmLft))
Location|S]: Junn', 'Xing' 'BusStopp)
APS
Agenti2):[Cye; 'Ped')
Action(@):(Bakke TTuLLft "Sttp',Incatihh "IncatRhi' "XingFmL Park)
Park')
Location(8: "IncLandl 'Dutgolanee' JJun', 'King', BBuSStpp', 'RhiPav))
Agent(2):[Cyc: 'Ped')
Refined Action/1y| XingFmLLt)
Refined Location/2] 'Jun', (BsSttp
RAPS
Agentzi:/Cye:: 'Pad')
Action(21:( "XingFmLiit /
Locafion(2): 'King', 'Outgolane')
KRPS
AgemtiZ)[Cyye; 'Ped')
Action|ty:t KingFmLLR" Refined Location|1)s Xing')
(a) Scene a pedestrian pushing bicycle and crossing the street from the Waymo/ROAD++ dataset with prediction sets using scoring functions for CP (Softmax, APS, RAPS) without and with KRPS.
Softmax
Agent(Z): (Cyy"l 'Ped')
Actioni7):(Turr.:: "TurRhe/Stopp 'Stop' 'IIcatthh'' "IncaaRht"/XingFmia 'King mRhtt, 'HazLit)
Coattion(l:OOuttoolmmee" JJun", 'IncLane', 'VehLane' 'iigg 'BuSStop')
KRPS
Agenti2): (Ped'
'Ped")
Action|2):(Xingfmm 'XingFmRhhe"
Location(2I(Jum (Xing'
APS
Agent[2]: (Cyc', 'Pad))
Action/5)(Brrake 'Turt.t:/Stop (IncatRhi, (ingaRhh.
Location(@:-VehLaeee IInLaane'Outgolane" Jun', 'Xing' /BusStop')
KRPS
Agent/2]: ('Cyel 'Pod")
Acciion/2)((XingFmm XXinFmRRhe)
Location(3:: Jun', 'ing', BBusStopp)
Agent(t): ('Ped)
Mctlio))):((Brakee 'Stop' (XingFiLLtt)
Location(2:(Paaringg 'Xing?
KRPS
Agent(1): (Ped')
(iction():(XinngELLL)
[ocation(1): "Xing"
(b) Scene of a pedestrian pushing a bicycle and crossing the street from the Waymo/ROAD++ dataset with prediction sets using 3 scoring functions for CP (Softmax, APS, RAPS) without and with KRPS.
Figure 5: Scenes from the Waymo/ROAD++ dataset with prediction sets using scoring functions for CP (Softmax, APS, RAPS) without and with KRPS.
tential prediction fails to meet both semantic and statistical criteria, KRPS opts to return an empty set, avoiding inaccurate or contextually inappropriate predictions. Conversely, traditional conformal prediction methods, which lack a semantic filter, tend to produce fewer empty sets but at the risk of including predictions that, although statistically plausible, might not align semantically with the context of the scene.
In Figure 7, we show qualitative example of situation where KRPS outputs empty set, while the RAPS does not. The scenario illustrates car for which the ground truth location is VehLane, which indicates a Vehicle lane. Applying RAPS using a = 0.5 leads to a prediction set including a single class, which is OutgoCycLane, referring to an Outgoing Cycle Lane. In contrast, when refining the prediction set with KRPS accordance with the agent class Car and the knowledge graph, KRPS yields an empty set. This outcome signals that none of the predicted locations applicable to the Car agent class, prompting considerations of potential anomalies, such mistakenly detected in cycle lane. It is important to note that had such scenarios been present

---

Percentage of Empty Sets by Alpha Level and Approach For the Location Task
1-softmax
1-softmaxKKRP5
APS
30
APS + KRPS
Percentage of Empty Sets
RAPS
RAPS KRPS
20
15-
0.1
0.2
0.3
0.4
0.5
or values
(a) Percentage of empty sets for different values of a for the location classification task.
Percentage of Empty Sets by Alpha Level and Approach For the Action Task
1-softmax
1-Softmax*KRPS
APS
35
APS+
Percentage of Empty Sets
RAPS
RAPS+KRPS
25
20
15
10-
0.2
a' values
(b) Percentage of empty for different values of for the action classification task.
Figure 6: Percentage of empty sets for different values of for the location and action classification tasks based w.r.t the knowledge graph and predictions of the agent class.
in the training data, the knowledge graph would have accounted for them, preventing KRPS from producing empty set under these conditions.
More on the Practicality of KRPS
While our paper focuses three high-level perception tasks for urban scene understanding, KRPS be extended to other robot perception applications with varying natures and number of tasks.
The formulation of Algorithm and Theorem 3.1 is adaptable diverse environmental contexts.
25

---

Detected agent class: ('Car") RAPS Location: {OutgoCycLanne)
KRPS: 0
Figure 7: Qualitative example of empty set generated by KRPS, using RAPS and a = 0.5.
For example, KRPS can be applied to urban search and rescue, where tasks such as victim detection, hazard identification, and robot action selection are critical [53]. In this scenario, the detection of victims informs subsequent hazard identification tasks by highlighting areas where hazards likely to be present. The results from hazard identification can then guide the action selection of the robot, such as navigating safely through debris or delivering emergency supplies. The role of external knowledge in the form of knowledge graphs or other forms of semantics can be decisive for the mission success [54]. KRPS enhances this application by ensuring that each prediction set semantically consistent with the preceding tasks and by providing uncertainty quantification, which crucial for making reliable decisions in high-stakes environments.
In the domain of robot manipulation, KRPS can significantly improve the accuracy and reliability of tasks such as object recognition, grasp strategy selection, and precise placement. Here, the clas- sification of objects directly influences the choice of the manipulation action [55]. For instance, identifying an object as fragile necessitates a more delicate grasping approach compared to a ro- bust item. Uncertainty quantification particularly important this context avoid mistakes such misidentifying object, which could lead improper handling and potential damage. KRPS ensures that each stage of the manipulation process is informed by the previous task's outcomes, enhancing both semantic consistency and decision reliability.
Additionally, KRPS can be utilized robotic navigation, especially in dynamic and unpredictable urban environments. The class of the robot's behavior, such as stopping, turning, or accelerating, can depend on the classes of agents present in the environment and their predicted future maneuvers [56, 57]. For example, the presence of pedestrian crossing the road might necessitate the robot to stop, while approaching vehicle could require the robot to yield or change lanes [51, 52]. In this application, KRPS provides a structured way to integrate these interdependent tasks, ensuring that navigation decisions are not only statistically valid but also semantically coherent with the surrounding context. This integration of uncertainty quantification and semantic consistency enables robots to navigate more safely and efficiently, adapting to complex real-world scenarios with greater reliability.
26


Reviews:
[{"review_id": "cXnytig4Fc", "reviewer": "Reviewer_Tzck", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "The paper proposes a new approach for uncertainty quantification for joint classification tasks: agent classification, action classification, and location classification. The approach uses a pre-defined semantic consistency knowledge graph, which is sued to eliminate class items from the predicted uncertainty set.", "summary_of_recommendation": "The paper is not well written would be my main complaint. As for the other two criticisms I mentioned, it would help the paper and the work become significant and attract attention.", "technical_quality": 1, "clarity_of_presentation": 1, "potential_impact": 1, "robotics_focus": 2, "quality_of_limitations": 2, "questions_for_rebuttal": "The authors are free to address any of the comments. I hope my suggestions will help the authors improve their paper.", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tOWiwlMMBD", "reviewer": "Reviewer_gYc2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "This paper introduces KRPS, Knowledge-Refined Prediction Sets, performing semantic-aware conformal prediction for multi-tasked perception. KRPS applies knowledge graph and cascaded CP to ensure the multiple prediction sets are semantically consistent. The method is validated on two AV perception datasets", "summary_of_recommendation": "I recommend acceptance of the paper. Overall it is a nice application of cascaded CP and knowledge graph for an important robotics problem. Despite the theoretical limitation, it shows promising improvement over baseline empirically.", "technical_quality": 4, "clarity_of_presentation": 4, "potential_impact": 3, "robotics_focus": 3, "quality_of_limitations": 3, "questions_for_rebuttal": "Is there any possible baseline that also tries to enforce semantic consistency among the prediction sets? Right now the baseline (standard) is pretty weak since it does not try to enforce the consistency at all, if I understand correctly.\n\nI recommend putting a reference for the \"1-softmax\" score. I know what you meant but the usual audience might not know. You can refer to it as LAC [1] and definitely add to a formal definition of it in the main text.\n\n[1] Mauricio Sadinle, Jing Lei, & Larry Wasserman. “Least Ambiguous Set-Valued Classifiers With Bounded Error Levels.” Journal of the American Statistical Association, 114:525, 223-234, 2019", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Srvkp3u01T", "reviewer": "Reviewer_8pRV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "This work proposes Knowledge-Refined Prediction Sets (KRPS), an extension of conformal prediction (CP) for multi-task classification. Specific focus is on the semantic consistency across tasks, which has not been studied before, while maintaining CP's marginal coverage. The presented approach leverages a knowledge graph, that is derived from common sense and the dataset labels, to generate a semantically consistent prediction set from multiple network outputs. The approach is evaluated on two datasets, ROAD and Waymo/ROAD++, using the standard CP metrics. Additionally, a new metric is introduced to evaluate semantic consistency, termed conditional semantic consistency metric.", "summary_of_recommendation": "The work introduces a novel approach for conformal predictions in multi-task classification, demonstrating convincing results on two datasets. Despite its strength, I have noted several areas of concerns that I would like the authors to address in their rebuttal.", "technical_quality": 4, "clarity_of_presentation": 4, "potential_impact": 3, "robotics_focus": 3, "quality_of_limitations": 3, "questions_for_rebuttal": "In addition to the weaknesses above, I found the following language issues:\n* L.202: The validation set is split into 3 sets, for validation, calibration and testing. Details on how these splits have been designed would facilitate reproduction of results.\n* Fig. 2 a): locations -> actions\n* L.218: with respect to s -> with respect to\n* L.237: location classification, location classification -> location classification, action classification", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l9TlLvlell", "reviewer": "Reviewer_UhpA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "This paper addresses the problem of developing a conformal prediction approach for multi-task classification problems, which occur commonly in perception tasks, e.g., in the case of autonomous driving. The authors combine a symbolic knowledge graph with existing conformal prediction methods, coupled with a correction procedure to account for accumulating errors over the multiple tasks. Evaluation is provided over the ROAD and Waymo/ROAD++ datasets.", "summary_of_recommendation": "The paper is well written overall, and the approach makes sense. I have a few concerns, which are outlined in the review and in the rebuttal questions.", "technical_quality": 3, "clarity_of_presentation": 3, "potential_impact": 2, "robotics_focus": 3, "quality_of_limitations": 2, "questions_for_rebuttal": "Can the authors describe the correction procedure and make sure to include in the final version, if accepted?\n\nCan the authors elaborate on how often the algorithm outputs empty sets in practice and why is that a fair comparison with standard conformal prediction?", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: strengths

- Reviewers recognize the paper is addressing an important research question, mentioning that "Ensuring consistency among prediction sets in the multi-tasked setting is a very important topic."
- clear applications:  KRPS is a natural and intuitive application of cascaded CP for AV perception.

weaknesses:

- Reviewer Tzck has concerns about the writing and presentation of this paper.
- "KRPS signalizes knowledge graph gaps or corner cases by producing empty prediction sets" not reflected in results.
- lack of explanation of how knowledge graphs can be built and its downstream effect on the prediction results.

After rebuttal, reviews for this paper remains divergent. However, the strong reject was mainly concerned about the writing and presentation of this paper, and the authors give a comprehensive revision on it. Since this paper is addressing an important research question, and the concerns on writing is non substantial and addressable, I would recommend accepting this work.
Decision: Accept