.png){kind=icon}
Return
MET-MAPF: A Metamorphic Testing Approach for Multi-Agent Path Finding Algorithms
.png){kind=icon}
OA
AI
DOI：10.1145/3669663.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Multi-Agent Path Finding (MAPF) problem, i.e., the scheduling of multiple agents to reach their destinations, has been widely investigated. Testing MAPF systems is challenging, due to the complexity and variety of scenarios and the agents' distribution and interaction. Moreover, MAPF testing suffers from the oracle problem, i.e., it is not always clear whether a test shows a failure or not. Indeed, only considering whether the agents reach their destinations without collision is not sufficient. Other properties related to the 'quality' of the generated paths should be assessed, e.g., an agent should not follow an unnecessarily long path. To tackle this issue, this article proposes MET-MAPF, a Metamorphic Testing approach for MAPF systems. We identified 10 Metamorphic Relations (MRs) that a MAPF system should guarantee, designed over the environment in which agents operate, the behaviour of the single agents and the interactions among agents. Starting from the different MRs, MET-MAPF automatically generates test cases addressing them, so possibly exposing different types of failures. Experimental results show that MET-MAPF can indeed find MR violations not exposed by approaches that only consider the completion of the mission as test oracle. Moreover, experiments show that different MRs expose different types of violations.
Keywords:
Multi-agent path finding
software testing
metamorphic testing
multiagent systems
agent interactions
Journal
A
IF:
6.2
Papers:
1.2K
Citations:
3.4K
Organization
Cited Papers
Treatment of massive pulmonary embolism utilizing a multidisciplinary approach: a case study.png)
Perfusion
PerfusionIF0
PREAI
ShareSaveShareSaveShareSave
View more