Detecting Non-Optimal Decisions of Embodied Agents via Diversity-Guided Metamorphic Testing

Wenzhao Wu, Yahui Tang, Mingfei Cheng, Wenbing Tang · 2025

Read Detecting Non-Optimal Decisions of Embodied Agents via Diversity-Guided Metamorphic Testing by Wenzhao Wu, Yahui Tang, Mingfei Cheng, Wenbing Tang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-20083.txt.

Introduction

Wenzhao Wu and five co-authors test embodied agents for how well they finish, not just whether they finish. An agent can succeed in a wasteful way. It can take detours and extra steps, and standard checks never notice. The team names such flaws non-optimal decisions. Their framework, NoD-DGMT, hunts them with metamorphic testing. Sound planners should act the same under set transforms of a task.

Four relations encode those optimality traits. They cover detours, action completeness, refinement, and scene changes. A diversity-guided selector picks test cases across flaw types. It avoids checking the same flaw twice. On the AI2-THOR simulator, with four top planning models, the tool found flaws in about a third of cases. It beat six baselines, and its diversity filter raised the hit rate further.

Catalog record

CREATORWenzhao Wu, Yahui Tang, Mingfei Cheng, Wenbing Tang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-20083

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Detecting Non-Optimal Decisions of Embodied Agents via Diversity-Guided Metamorphic Testing Thanks: W. Wu is with the National Supercomputing Center, Wuxi, Jiangsu 214072, P. R. China (E-mail: [email protected]). Thanks: Y. Tang is with the School of Computer, Chongqing University of Posts and Telecommunications, Chongqing, 400065, P. R. China (E-mail: [email protected]). Thanks: M. Cheng is with the School of Computing and Information Systems, Singapore Management University, Singapore 188065 (E-mail: [email protected]). Thanks: W. Tang is with the College of Information Engineering, Northwest A&F University, Yangling, Shaanxi 712100, P. R. China (E-mail: [email protected]). Thanks: Y. Zhou is with the School of Computer Science and Technology, Zhejiang Sci-Tech University, Hangzhou, Zhejiang 310018, P. R. China (E-mail: [email protected]). Thanks: Y. Liu is with the College of Computing and Data Science, Nanyang Technological University, Singapore 639798 (E-mail: [email protected]). Wenzhao Wu, Yahui Tang, Mingfei Cheng, Wenbing Tang Abstract As embodied agents advance toward real-world deployment, ensuring optimal decisions becomes critical for resource-constrained applications. Current evaluation methods focus primarily on functional correctness, overlooking the non-functional optimality of generated plans. This gap can lead to significant performance degradation and resource waste. We identify and formalize the problem of Non-optimal Decisions (NoDs), where agents complete tasks successfully but inefficiently. We present NoD-DGMT , a systematic framework for detecting NoDs in embodied agent task planning via diversity-guided metamorphic testing. Our key insight is that optimal planners should exhibit invariant behavioral properties under specific transformations. We design four novel metamorphic relations capturing fundamental optimality properties: position detour suboptimality, action optimality completeness, condition refinement monotonicity, and scene perturbation invariance. To maximize detection efficiency, we introduce a diversity-guided selection strategy that actively selects test cases exploring different violation categories, avoiding redundant evaluations while ensuring comprehensive diversity coverage. Extensive experiments on the AI2-THOR simulator with four state-of-the-art planning models demonstrate that NoD-DGMT achieves violation detection rates of 31.9% on average, with our diversity-guided filter improving rates by 4.3% and diversity scores by 3.3 on average. NoD-DGMT significantly outperforms six baseline methods, with 16.8% relative improvement over the best baseline, and demonstrates consistent superiority across different model architectures and task complexities. I Introduction While foundation models, such as Large Language Models (LLMs) and Vision-Language-Action (VLA) models, have demonstrated impressive capabilities in natural language understanding, multimodal reasoning, and content generation, they remain fundamentally disembodied and lack the ability to directly interact with the physical world [ 1 ] . This trend has led to the emergence of embodied AI [ 2 , 3 , 4 ] , where embodied agents are equipped with physical forms such as robots, enabling them to actively perceive, learn from, and interact with the physical environment. Consequently, embodied agents are widely regarded as a pivotal step toward achieving Artificial General Intelligence (AGI), given their potential in various real-world applications [ 5 , 6 , 7 , 8 , 9 ] , such as household services, industrial manufacturing, healthcare, and autonomous driving. In embodied agents, task planning constitutes a fundamental capability that encompasses the decision-making processes required to decompose complex task objectives into executable action sequences [ 10 , 11 ] . This involves sophisticated multi-dimensional reasoning, wherein agents must interpret natural language instructions, accurately assess environmental states and constraints, and effectively coordinate interdependencies among sequential subtasks [ 12 ] . The resulting action plans must be both computationally feasible and contextually appropriate for successful task execution. Recently, numerous studies have explored leveraging LLMs for embodied task planning, demonstrating promising performance and enhanced adaptability [ 13 , 10 , 14 , 15 ] . As these agents become increasingly deployed in safety-critical and resource-sensitive scenarios, ensuring the quality and reliability of their decisions becomes paramount. However, existing evaluation methods for embodied agents primarily focus on basic functional requirements, such as task success rates [ 16 , 17 , 18 ] , trajectory length [ 19 , 20 ] , and execution time [ 10 ] . Although these functional metrics provide valuable insights into task completion capabilities, they fail to capture crucial non-functional requirements essential for real-world deployment. One important yet underexplored aspect is optimality, which is the ability to make decisions that minimize resource consumption and maximize efficiency through the most effective means possible. While Non-optimal Decisions (NoDs) do not compromise task completion, they can result in substantial cost increases and resource inefficiencies in practical scenarios. For instance, suboptimal planning in household service robots may lead to excessive energy consumption and user frustration due to prolonged operation times. Therefore, developing a comprehensive framework to systematically detect and evaluate NoDs is imperative for ensuring practical utility and cost-effectiveness in resource-constrained deployment scenarios. Systematically detecting and evaluating NoDs in embodied agents presents several significant challenges. First, unlike functional testing with explicit criteria (e.g., task completion rates), optimality assessment lacks clear oracles for determining the “optimal” action sequence across diverse scenarios and contexts. Second, ensuring comprehensive NoD detection is challenging, as evaluation processes may repeatedly identify similar suboptimal patterns while overlooking other violation categories, thereby limiting coverage comprehensiveness. Third, while functional testing relies on direct input-output comparisons, optimality evaluation requires establishing meaningful comparison criteria and appropriate metrics to assess the relative performance of different decision sequences. To address these challenges, we propose NoD-DGMT , a novel Diversity-Guided Metamorphic Testing (MT) framework designed to detect NoDs in embodied agent task planning. Specifically, we first identify and formalize four Metamorphic Relations (MRs) that capture the invariant properties of optimal decisions, enabling optimality assessment without explicit oracles. Second, we define diversity metrics and propose a diversity-guided selection strategy that filters and prioritizes test cases with greater variations to ensure comprehensive evaluation coverage across different types of potential NoD patterns. Finally, we develop an MT-based detection framework that leverages the identified MRs and diverse test cases to automatically evaluate decision optimality and quantify violation severity. We conduct comprehensive experiments to evaluate the effectiveness and efficiency of NoD-DGMT using the AI2-THOR simulator [ 21 ] . First, we demonstrate NoD-DGMT ’s effectiveness across varying task complexities with four different planners, successfully detecting NoDs with violation rates ranging from 18.7% to 67.2%. Second, ablation studies validate our diversity-guided filter, showing it enhances detection efficiency by 4.3% while improving diversity coverage. Finally, comparison with four baseline methods demonstrates NoD-DGMT ’s superiority, achieving 31.9% average detection rate while baseline methods achieve only 5.7%. The main contributions of this paper are as follows. • We propose NoD-DGMT , the first MT-based framework to evaluate the optimality of embodied agent decisions. • We introduce four innovative MRs and a diversity-guided test case filter to systematically and efficiently discover diverse NoDs. • We conduct extensive evaluations across multiple planners, various task complexities, and different testing scenarios, to demonstrate the effectiveness and efficiency of NoD-DGMT . The rest of this paper is organized as follows. Section II introduces the background. Section III presents the motivation and problem statement. The detailed procedures of NoD-DGMT are provided in Section IV . Experiments are conducted in Section V to demonstrate the effectiveness and efficiency of our approach. Section VI summarizes the related work. Finally, Section VII presents the discussion and conclusion. II Background II-A Embodied Task Planning Embodied task planning is a process to generate a sequence of executable actions to accomplish the given goal within a physical environment [ 10

Read the complete text