Adaptive Random Testing for Multiagent Path Finding Systems

doi:10.1109/TR.2022.3146323

Return

Adaptive Random Testing for Multiagent Path Finding Systems

2022-03-01

PRE

Yang Liu

Xiao–Yi Zhang *

DOI：10.1109/TR.2022.3146323

Original

Original request for help

Save

Abstract

En 中文

The multiagent path finding (MAPF) problem identifies the scheduling of multiple agents simultaneously, such that all of them can reach their targets efficiently. To date, MAPF systems have been assigned important tasks such as traffics and warehouses. It is essential to conduct testing for MAPF systems to detect potential failures. Namely, in an MAPF system, a test case is a specific MAPF scenario, including the initial locations of the agents and the environment for these agents to play in. By testing, we intend to find the scenarios (i.e., test cases) whose executions reveal failures. Testing MAPF systems is challenging due to the complexity of its input and the interactions among multiple agents. This article proposes the testing approach based on the adaptive random testing (ART) for MAPF systems. ART aims to generate new test cases far from the already executed ones. Particularly, to calculate the distance between each pair of test cases, we introduce two metrics, the initial density distribution and the destination density distribution, to characterize the distribution of the agents' initial and destination nodes, respectively. Benefit from ART, the diversity of the information generated during testing can be improved. Experimental results show that compared with the random testing, our approach can detect more diverse failure-revealing scenarios.

Keywords:

Measurement

Adaptive systems

Job shop scheduling

Scalability

Subspace constraints

Benchmark testing

Planning

Adaptive random testing (ART)

density measurement

multiagent path finding (MAPF)

multiagent systems