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: robot-learning_org_CoRL_2024_Conference
Published: 2024-06-06 11:10:48

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.

Main paper: 
 introduction: 
 In urban environments, autonomous systems are tasked with navigating complex and dynamic scenes, necessitating robust decision-making mechanisms that can interpret diverse elements with a high-level semantic understanding. To reason about the scene, autonomous systems perform a series of critical tasks, distinguishing between different types of agents like pedestrians and vehicles, understanding their actions such as 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 it essential to integrate semantically-aware reasoning with uncertainty quantification. Combining semantic and uncertainty awareness allows autonomous agents to make reliable and contextually appropriate decisions, adapting to the urban landscape dynamically.Conformal prediction (CP) [10, 11, 12] emerges as a versatile approach for uncertainty quantification in learning-based models. Compared to other uncertainty quantification frameworks in deep learning, such as Bayesian networks [13] , Radial Basis Functions networks [14] , and evidential learning [15] , CP provides uncertainty-aware predictions by generating prediction sets that are theoretically guaranteed to include the correct class with user-defined confidence. The guarantees offered by CP-based frameworks ensure the reliability of the underlying systems, a 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-Figure 1 : An example of refined sets using KRPS on a 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 are 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, 21] , 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 to the logical alignment of predictions across different tasks, ensuring that the inferred attributes are contextually appropriate and mutually compatible. To illustrate this, we present in Figure 1b the result of one of our experiments on 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 is 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-Refined Prediction Sets (KRPS), a novel CP approach that reduces uncertainty in autonomous agents in urban environments by producing valid, uncertainty-aware prediction sets that are semantically consistent across multiple tasks. KRPS consists of a knowledge graph that links the different tasks, and a sequential1 set construction procedure based on an intial task to ensure the produced 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 predictions, based on initial task results. As depicted in Figure 1c , 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 to 80% lower uncertainty when compared to traditional CP, reflected by the lower number of classes in the prediction 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, introducing the concept of conditional semantic consistency for multitask-based autonomous perception and demonstrating the semantic consistency and marginal coverage properties of the produced sets. We evaluate KRPS on 2 large-scale autonomous driving datasets, namely the ROAD dataset [1] and Waymo/ROAD++ dataset [24] , from the scope of 3 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-art conformal 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. 
background on conformal prediction: 
 We focus on CP for classification, as it is the relevant task for our work. Let g θ be a classifier pre-trained on a dataset D train . The model g θ outputs estimated probabilities for each class (e.g., softmax scores), such that g θ (X) ∈ [0, 1] K , where X is an input image and K is 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 D train , to which we refer to as calibration set D cal . The goal of CP is to construct prediction sets for unseen data samples C(X test ) that are valid, i.e., they contain the true label Y test with a probability 1 -α, where α is a user-defined error rate. This property is called marginal coverage and is expressed in Equation 1.EQUATIONTo construct the prediction sets, CP requires a 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 D cal are ranked, and the empirical 1 -α quantile q is calculated.  
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-aware and semantically consistent predictions. We focus on 3 classification tasks: agent type, agent location, and agent action, that are deemed necessary to achieve a high-level semantic understanding of the robot's environment [1, 2, 3, 4] . We assume the existence of 3 separate neural networks g c , g l , and g a that output the agent class Ŷ c j ∈ Y c , agent location class Ŷ l j ∈ Y l , and agent action class Ŷ a j ∈ Y a , respectively, given a bounding box around the agent of interest X j , where X j ∈ X , and X represents the set of all agents of interest in a scene. Given the models g c , g l , and g a , a calibration set D cal , and an unseen test sample X test , our goal is to sequentially construct the prediction sets C l (X test ) for location classification, and C a (X test ) for action classification, given a C c (X test ) that was generated by an agent classification CP algorithm. We opt for sequential task refinement as it permits on-demand processing of subsequent tasks in case of need. We desire our generated sets to have two properties. The first property is marginal coverage as described in Equation 1, which means that the predicted sets are guaranteed to include the true label Y test with a probability of at least 1 -α. 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 c (X test ) = {car, medium vehicle, large vehicle} it is clear that Y test corresponds to a vehicle, and so C l (X test ) 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, we 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 remainder of this paper, we refer to sets constructed by KRPS by C KRP S c (X test ), C KRP S l (X test ), and C KRP S a (X test ).KRPS consists of two components: a knowledge graph and a knowledge-based multitask conformal prediction algorithm. The knowledge graph models the semantic relationships between the different tasks we consider. For a particular agent class, only a 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 a 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 relationships between the tasks are constructed as follows. Given a task T c and T a referring to the tasks of agent classification and agent action classification, K contains a set-valued deterministic functionM c→a : Y c → 2 Y athat 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 M c→l , and to all its possible actions by M c→a . Given K, we introduce the notion of conditional semantic consistency between prediction sets for each task. Definition 3.1 (Conditional Semantic Consistency) Let C j and C i be 2 prediction sets containing class candidates for the tasks T j and T i , respectively. C i is semantically consistent with respect to C j and K, if: KRPS Construction Procedure. KRPS is based on sequentially pruning prediction sets using knowledge from K. For a given scene and an object X test , we start by constructing the prediction set for the agent class task C KRP S c (X test ). Since our approach is sequential, the construction procedure of the prediction set for the first task follows the usual CP procedure based on Theorem 2.1. Next, we acquire all possible locations of agent classes in C KRP S c (X test ) using the semantic mapping from the knowledge graph K. The set of all possible locations that correspond toEQUATIONC KRP S Ti , i ∈ [1, m]: semantically consistent prediction sets. 1 C KRP S T0 ←•Y 0 2 P Ti ← 1,∀Y Ti ∈ Y Ti , i ∈ [0, m] 3 for i = 1 to m do 4 C K Ti ←•M Ti-1→Ti (C KRP S Ti-1 ) 5 C KRP S Ti ←{} 6 for y ∈ C K Ti do 7 P Ti ←M(p-value(X test , D cal )) 8 if P Ti ≥ α then 9 C KRP S Ti ← C KRP S Ti ∪ {y}C KRP S c (X test ) is C K l = M c→l (C KRP S c) 2 . We use C K l as a starting set for further pruning, instead of considering the full space of labels Y l . The pruning consists of a conformal prediction step based on a conformity score proper to the location classification task. Examples of such conformity scores are 1 -Sof tmax. The conformal prediction step produces the set C KRP S l . Applying the steps described above results in a multihypotheses testing problem, where the familywise error increases. To account for the MHT problem, applying a correction procedure M of the 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 C KRP S l . Using the procedure explained above, the generated sets are guaranteed to be semantically consistent and to have coverage as formalized in Equation 1. The KRPS set construction proce-2 M c→l is a point to set mapping. We abuse the notation to indicate the set of images for every elements in C KRP S c using the mapping M c→l . dure is formalized in Theorem 3.1 and described in Algorithm 1. The proof of Theorem 3.1 and its corollary, along with an analysis of their practical implications, are provided in Appendix A.Theorem 3.1 (Knowledge-Refined Conformal Prediction) Given 2 tasks T c and T l , the semantic mapping function M c→l , and the prediction sets C c (X test ) and C l (X test ), the setC KRP S l (X test ) = C l (X test ) ∩ M c→l (Y c test ) is semantically consistent with respect to C KRP S cand K, and satisfies the marginal coverage described in Equation 3.EQUATIONWe prove this property by leveraging the probability conservation of the deterministic semantic mappings between the task and proposing a generalizing of the cascaded CP Theorem [25] to cover multitask settings. We present the detailed proof of Theorem 3.1 in Appendix A. 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 2 state-of-the-art approaches, using 2 widely used CP metrics: deviation from coverage rate and set size. Since we are the first to consider semantic consistency across tasks in CP, we introduce a metric for semantic consistency.The ROAD Dataset [1] . The Road Event Awareness dataset (ROAD) for autonomous driving includes 22 videos, and 1.7M labels across 11 agent classes, 15 locations, and 23 actions under various weather conditions, providing a diverse and challenging set of scenarios for testing the effectiveness of KRPS. ROAD offers (agent, location, action) triplets, ideal for a comprehensive evaluation.The Waymo/ROAD++ Dataset3 . The Waymo/ROAD++ dataset, an extension of the ROAD dataset, incorporates 3.5M agents, 4.3M actions, and 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, we use the 3D-RetinaNet [1] with separate heads for each classification task, outputting softmax scores. The model is trained on each dataset for 30 epochs with an Adam optimizer at a learning rate of lr = 0.001. We randomly divide the validation splits of both datasets in 3 equal-sized portions as follows: eval split 1 for validation, eval split 2 for calibration, and eval split 3 for testing. All experiments use Bonferroni correction for prediction robustness, with results averaged over 100 trials on a single 24GB RTX 3090. 4Deviation from Target Coverage (DTC). The deviation from the target coverage rate (DTC) quantifies the discrepancy between the achieved coverage, Cov approach , and the desired target coverage, Cov target = 1 -α, as defined in Equation 4.EQUATIONNegative DTC values indicate coverage below 1 -α, indicating a 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 a trivial output for CP-based methods to achieve the coverage guarantees, a 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 i with respect to T i-1 and K. For a prediction set C T i , semantic consistency represents the rate of semantically consistent classes in the entire set and is formulated in Equation 5. A higher semantic consistency value demonstrates better coherence between the prediction sets across the tasks.EQUATIONInspired 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 -Sof tmax [27] , and 2 state-of-the-art CP scores. The first approach is adaptive predictive sets (APS) [28] , which is a scoring technique known to improve conditional coverage. The second approach is regularized adaptive predictive sets (RAPS) [29] , which is known to 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.Our evaluation considers 3 tasks on both datasets, namely agent, location, and action classification.Since our approach acts sequentially on 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 tmax, APS, and RAPS. Using the predicted agent class sets, we report the results for the subsequent tasks: location classification, and action classification. In Appendix C, We report the results of longer task sequences using 3 tasks to show the capability to handle longer sequences of tasks with different orders.We conduct our evaluation using different values of α 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 1a and 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 is 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 on longer task sequences, the influence of the knowledge graph size, and the percentage of the empty sets in Appendices B, and E, respectively. 
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 Language Models (LLMs) are increasingly used to enhance autonomous navigation [38, 39, 40, 41] . These models, prone to uncertainty and hallucinations [42] , necessitate a detailed contextual understanding of the scene for effective operation [43] . Incorporating semantic awareness and uncertainty awareness enhances both the reliability and interpretability of these systems, addressing a fundamental 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 a practical approach to consider uncertainty and semantic awareness in autonomous robots and systems, it is important to consider the limitations of its application. KRPS, being a CP-based approach, traditionally relies on the assumption of data exchangeability. This assumption can limit its effectiveness with scoring functions that fail to address out-ofdistribution (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 integrity of the underlying knowledge graph. Ambiguities within the knowledge graph regarding class definitions can compromise prediction accuracy. To address this, our evaluation integrates ontological structures derived from the datasets utilized, such as ROAD and Waymo [1, 24] , and aligns with established logical frameworks [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 ontologies. KRPS is 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 to better efficiency.Practicality. While our paper focuses on 3 high-level perception tasks for urban scene understanding, KRPS can be extended to other robot perception applications. The formulation of Algorithm 1 and Theorem 3.1 is adaptable to diverse environmental contexts. For example, KRPS can be applied 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 as robot manipulation, where a 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. 
conclusion: 
 We introduced KRPS, a Knowledge-Refined Prediction Set approach, tailored for multitask learning in urban scene understanding. By refining prediction sets through semantic relationships among tasks, KRPS ensures semantic consistency and adheres to coverage guarantees by producing significantly smaller prediction sets. KRPS shows promise for real-world applications, particularly in autonomous driving. Theorem A.1 (Cascaded-CP [25] ) For any sequence of non-conformity measures (S 1 , ..., S m ), which yields p-values (P 1 , ..., P m ) and α ∈ [0, 1], the prediction set C j (X test ) at step j < m is defined as:EQUATIONwhere P y j is the corrected p-values using the procedure M for candidate y at step j. Then ∀j ∈ [1, m], C j (X test ) satisfies Equation 1, and C m (X test ) ⊆ C j (X test ). EQUATIONBased on Equations 11 and 12, we can establish that:EQUATIONWhich gives that C KRP S a is semantically consistent with respect to C KRP S c and K.Implications of Corollary 3.1 Corollary 3.1 establishes the transitive properties of semantic consistency, as defined using Definition 3.1. As depicted in Figure 3 , this result implies that two prediction sets from sequential tasks maintain semantic consistency, even if constructed independently, as long as they are built in sequence relative to a shared task in the middle. This finding holds significance 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 consistency for the latest executed task.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 to ensure broad applicability and robustness across various operational scenarios [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 sets are semantically consistent given the output of the first task and according to the relationships defined in the knowledge graph, this consistency is conditional on those of initial outputs of the first task executed. 
 
 Appendix: In our implementation of KRPS, addressing the challenges of multiple hypothesis testing is crucial due to the simultaneous consideration of multiple semantic categories in the knowledge graph. To ensure the validity of our statistical inferences while managing the family-wise error rate (FWER), we employ the Bonferroni correction procedure. The Bonferroni procedure [50] is a conservative approach that adjusts for multiple comparisons by dividing the desired significance level α by the number of hypotheses tested, m.Specifically, if individual tests are conducted at a significance level α, the Bonferroni correction modifies the significance threshold for each test to α m . For KRPS, where each agent's classification can lead to multiple related hypotheses about actions and locations, the correction ensures that the overall probability of making one or more type I errors does not exceed α.Mathematically, this is represented as:α adjusted = α mWhere m 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 α, KRPS maintains the control over the error rates across all tests.In the following, we provide more details about the knowledge graph used to model the semantic relationships between the entities in the urban environment. We adopt a simple, yet effective ontological 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 a single model. This is to ensure that we consider a multitask setup, in contrast to situations where a model outputs a triplet, which we consider as a case of multi-class classification tasks.We adopt the class labels provided by the ROAD and the Waymo/ROAD++ datasets5 [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 M Ti→Tj , where T i and T j 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 coherent 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 a structured dictionary. The construction procedure ensures also that the reverse mappings can be queried, in case a 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 semantically 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, a 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 knowledge graph construction procedure. Even if the knowledge from the training set is incomplete, KRPS 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.It is important to acknowledge that the construction of knowledge graphs can be approached through various methodologies beyond the one implemented in KRPS. The method described herein was selected for its simplicity and effectiveness within our 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. Load ground truth labels from GT f ileExtract 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-dictionary for actions and locations Populate the boolean arrays using triplet data: In the following, we detail the finalized knowledge graph utilized in our implementation. Table 5 summarizes the semantic mappings M c→a and M c→l . The semantic mappings M a→c and M a→l are represented in Table 6 . Finally, the semantic mappings M l→c and M l→a are represented in Table 7 .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 is varied at In Section 4.5, we reported results for sequences of 2 tasks: {agent → location} and {agent → action} for α = [0.1, 0.2, 0.4]. In the following, we present more results on both datasets for the full set of values of α = [0.1, 0.2, 0.3, 0.4, 0.5] for the sequences {agent → location} and {agent → action} in Table 9 and Table 10 , respectively. Furthermore, we present results using sequences of 3 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: Seq1 : {agent → action → location}, and Seq2 : {location → action → agent}. We use the same evaluation set-up and data splits reported in the evaluation section in our paper. The results are reported in Table11 and Table 12 , respectively.In all task sequences, KRPS still holds the theoretical coverage guarantees for all values of α. More importantly, KRPS achieves the desired coverage rates while being able to reduce the set size considerably. The conditional semantic consistency also holds, as it is guaranteed by Theorem 3.1 and Corollary 3.1. For all task sequences, the conditional semantic consistency for task 2 with respect to task 1 and K, task 3 with respect to task 2 and K, and task 3 with respect to task 1 and K, is 100%.In this section, we present further qualitative results on the ROAD and Waymo/ROAD++ datasets for the task sequences {agent → action}, {agent → location}, and {agent → action → location}. Figure 6a shows a scene with a car stopping in the outgoing lane. The prediction sets for the action and location classification tasks demonstrate how KRPS achieved a 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.Figure 4b shows a scene with a bus stopping in the vehicle lane. All approaches succeed in including the correct labels in the prediction sets. The combination of KRPS with RAPS succeeds in constructing a singleton for the tasks location and action classification. By applying KRPS, the action and location that are not relevant to the agent class are removed.Figure 6b showcases a 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.Figure 4 : Scenes from the ROAD dataset [1] with prediction sets using 3 scoring functions for CP (Softmax, APS, RAPS) without and with KRPS.Figure 5 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 a low-light scenario where a pedestrian crosses the street with a car in the background 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 classification 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 a scenario where a pedestrian is crossing the street while pushing a 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.In the KRPS framework, the occurrence of empty prediction sets is a 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 semantic and statistical criteria established 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 exceeds 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 knowledge graph. This integration means that even if a 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 a trend where 1 -Sof tmax, APS, and their combination with KRPS produce more empty sets as the value of α 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 α. This is an expected behavior since the regularization term in RAPS encourages the inclusion of additional labels if the set is 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 a po- 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 a qualitative example of a situation where KRPS outputs an empty set, while the RAPS does not. The scenario illustrates a car for which the ground truth location is VehLane, which indicates a Vehicle lane. Applying RAPS using α = 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 in accordance with the agent class Car and the knowledge graph, KRPS yields an empty set. This outcome signals that none of the predicted locations are applicable to the Car agent class, prompting considerations of potential anomalies, such as a car mistakenly detected in a cycle lane. It is important to note that had such scenarios been present in the training data, the knowledge graph would have accounted for them, preventing KRPS from producing an empty set under these conditions.F More on the Practicality of KRPS While our paper focuses on three high-level perception tasks for urban scene understanding, KRPS can be extended to other robot perception applications with varying natures and a number of tasks. The formulation of Algorithm 1 and Theorem 3.1 is adaptable to diverse environmental contexts.Detected agent class: {'Car'} RAPS Location: {OutgoCycLane} KRPS: {} 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 are 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 is semantically consistent with the preceding tasks and by providing uncertainty quantification, which is 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 classification 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 robust item. Uncertainty quantification is particularly important in this context to avoid mistakes such as misidentifying an object, which could lead to 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 in 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 a pedestrian crossing the road might necessitate the robot to stop, while an 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.Sequentiality in our context means refining predictions for one task at a time.Waymo/ROAD++: https://sites.google.com/view/road-plus-plus/datasetOur code is available here: https://gitlab.com/achref.d/krps.Waymo/ROAD++: https://sites.google.com/view/road-plus-plus/dataset 


Decision: 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.

Reviews: review: title: title: Not Well Written. Reject.
paper_summary: paper_summary: 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.
main_review: main_review: 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. 

I have three major criticisms of this work:  
- The paper is not written well. A simple idea is explained painstakingly and in a very non-intuitive manner. 
- The rules in perception cannot be hard coded as the authors are proposing here. For example, in Fig  2b, it shows that the class "Cyclist" can only be at the crossing or in the cycle lane. This, however, is not true in practice. It is very much possible for the cycle to be in the middle of the road. Therefore, the method seems to introduce some systematic error into the proposed CP model. I believe this is a major limitation of this approach of reducing the uncertainty set. 
- Even if you could codify these rules, the authors do not comment on the scalability of this approach. How many such rules would one have to codify for an application setting like autonomous driving? Is it even practicable? 

Specific points to improve the paper: 
- The introduction is too verbose and repetitive. Semantic consistency is mentioned several times. The Introduction mainly markets the work, i.e., it argues that the proposed method produces smaller uncertainty set that is semantically consistent. A good introduction provides an overview of the method; however, this is not available in the introduction. A good introduction also provides the scope of the work. This is not made clear in the introduction leading a reader to conclude that the approach is generally applicable.
- It is not clear what "value()" is in an in-line equation in the statement of Theorem 2.1.
- The notion of "semantic consistency" remains unclear till Section 3 of the paper. The paper argues that the methods is aimed to enforce "semantic consistency." However, it should be made clear if they mean "semantic consistency" in a colloquial sense or in an exact definitional sense. It is only in Definition 3.1 that it becomes clear that the authors have a very specific, rule-based specification of "semantic consistency."
- In Section 3, the paper states "the goal is to sequentially construct the prediction set C_l(X_test) for location classification and C_a(X_test) for action classification, given a C_c(X_test) that was generated by an agent classification CP algorithm."
	- It is unclear: "why sequentially?" or "what is sequential here." Up to this point, there has been no indication of it. 
	- Given agent classification set seems like a new problem scoping here. The paper did not mention this in the beginning, i.e., the paper considers some form of a conditional model of prediction class first, and then the rest --- namely action and task. Scoping the problem in the beginning would be helpful to the reader. 
	- Given this line, why does the last line state that the KRPS also predicts C_c^{KRPS}(X_test)? Isn't C_c predicted independent of the proposed KRPS method?
- In Definition 3.1, are "a" and "c" generic notations or specific to agent action and agent class? If they are generic, it is better to use different different labels than "a" and "c."
- In Definition 3.1, what does "/" mean in Eq (2)? It is not common a mathematical notation.
- The line after Eq (2): should it be "M_{a->c}" instead of "M_{c -> a}"? This statement is unclear, as Eq(2) speaks about image of Y_a in the mapping M_{a -> c}. How do you deduce the pre-image in C_c is not clear.
- The notation "M_{c->l}(C_c)" on line 153 is not correct. The mapping M_{c->l} is defined from point to set, and not set to set (ref: line 131).
questions: questions: The authors are free to address any of the comments. I hope my suggestions will help the authors improve their paper.
limitations: limitations: 2
review_summary: review_summary: 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.
title: title: Well-executed paper despite limitations
paper_summary: paper_summary: 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
main_review: main_review: Strength:

1. Ensuring consistency among prediction sets in the multi-tasked setting is a very important topic. KRPS is a natural and intuitive application of cascaded CP for AV perception. The method is well executed.

2. The paper is written cleanly and easy to read.

3. The quantitative results are quite strong — although I am curious if there is any other baseline that can be considered

Limitation:

1. If I understand correctly, there is no probabilistic guarantee for three sets being semantically consistent w.r.t. each other. I guess this is why DTC is fairly large in some experiment settings.  

2. It would be good to visualize the knowledge graph more in the main text. The audience might be curious about how complex it is.

3. The coverage right now is marginal, that the guarantee holds in expectation over the calibration sets. Ideally we would like to get coverage conditioning on a particular calibration dataset.

4. I think this approach can be applied in other settings beyond AV. I know the authors choose to focus on AV, but I think some examples in other domains such as navigation or manipulation would strengthen the paper a lot.
questions: questions: 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.

I 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.

[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
limitations: limitations: 3
review_summary: review_summary: 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.
title: title: Official Review of Submission 283 by Reviewer 8pRV
paper_summary: paper_summary: 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.
main_review: main_review: The following summarizes strength and weeknesses of the paper.

### Strength
1) The proposed method for semantic-aware CP is novel. The provided mathematical proofs strenghten the generality of the approach.
2) The manuscript is well structured, the notation is well defined and the experimental setup is well-suited for the evaluation of the approach.
3) The results are produced using standard CP metrics, where KRPS outperforms the baseline scoring functions throughout all metrics.
4) The commitment to publish the code upon acceptance is commendable.

### Weaknesses
1) The authors mention that KRPS signalizes knowledge graph gaps or corner cases by producing empty prediction sets. I don't see this reflected in the results, neither in the quantitative nor qualitative evaluation. A discussion and qualitative examples would be helpful.
2) The evaluation assumes a given knowledge graph, however building knowledge graphs can be difficult in practice. A study of how the quality of the knowledge graph influences the results would be helpful to understand the dependency.
questions: questions: In addition to the weaknesses above, I found the following language issues:
* 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.
* Fig. 2 a): locations -> actions
* L.218: with respect to s -> with respect to
* L.237: location classification, location classification -> location classification, action classification
limitations: limitations: 3
review_summary: review_summary: 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.
title: title: Review
paper_summary: paper_summary: 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.
main_review: main_review: Overall, the paper is well written. Conformal prediction is
an important and promising direction for high-dimensional
settings such as perception. The neuro-symbolic approach
seems like a natural extension of standard conformal
prediction. I also appreciate the evaluation over two
different case studies. I do have a few comments that
can be used to improve the paper, however.

My first comment has to do with the knowledge graph
construction. The authors do list this as one of the
method's limitations but it is not clear how well such
graphs can be constructed from high-dimensional data.
The authors at one point mention that implications can
be developed from common sense but such a manual
approach is unlikely to scale and generalize beyond
very simple scenarios.

Related to the above, the proposed method may
output an empty prediction set but it is not clear
how often that happens and whether it may be an issue
in practice. The authors are encouraged to elaborate on
this issue since standard conformal prediction is
designed to be conservative -- thus, the comparison
may be unfair.

One more related comment is that the correction
procedure is not explained anywhere in the main body
or in the appendix. What does this correction entail?
Presumably the first task may need to include more
labels in the predicted set so as to ensure conformity
over all tasks? It is essential to include this in
the paper, otherwise it would be incomplete.

Technical:

- The authors mention in a few places that the DTC
  metric must be positive but I am not sure if this
  is correct. The conformal sets are averaged over
  a validation set, so I would expect the DTC to hover
  around 0 if the method is well calibrated (but 
  positive and negative numbers should be equally
  likely).
- Typo in Fig. 2a: The bottom location should say 
  "Set of all possible actions"
questions: questions: Can the authors describe the correction procedure and make sure to include in the final version, if accepted?

Can the authors elaborate on how often the algorithm outputs empty sets in practice and why is that a fair comparison with standard conformal prediction?
limitations: limitations: 2
review_summary: review_summary: 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.