Safety validation of sense and avoid algorithms using simulation and evolutionary search

Xueyi Zou; Rob Alexander; John Alexander McDermid

Safety validation of sense and avoid algorithms using simulation and evolutionary search

Xueyi Zou, Rob Alexander, John Alexander McDermid

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

We present a safety validation approach for Sense and Avoid (SAA) algorithms aboard Unmanned Aerial Vehicles (UAVs). We build multi-agent simulations to provide a test arena for UAVs with various SAA algorithms, in order to explore potential conflict situations. The simulation is configured by a series of parameters, which define a huge input space. Evolutionary search is used to explore the input space and to guide the simulation towards challenging situations, thus accelerating the process of finding hazards and supporting the validation process. We applied our approach to the recently published Selective Velocity Obstacles (SVO) algorithm. In our first experiment, we used both ran-dom and evolutionary search to find mid-air collisions where UAVs have perfect sensing ability. We found evolutionary search can find some hazards (here, interesting problems with SVO) that random search takes a long time to find. Our second experiment added sensor noise to the model. Random search found similar problems as it did in experiment one, but the evolutionary search found some interesting new problems. The two experiments show that the proposed approach has potential for safety validation of SAA algorithms

Original language	English
Number of pages	16
Publication status	Published - 2014
Event	33rd International Conference on Computer Safety, Reliability, and Security, SAFECOMP 2014 - Florence, United Kingdom Duration: 10 Sept 2014 → 12 Sept 2014

Conference

Conference	33rd International Conference on Computer Safety, Reliability, and Security, SAFECOMP 2014
Country/Territory	United Kingdom
City	Florence
Period	10/09/14 → 12/09/14

Access to Document

Safety Validation of Sense and Avoid Algorithms using Simulation and Evolutionary Search FinalAccepted author manuscript, 2.91 MB

Cite this

@conference{e859b07a17a34691b0ef9cb8e4dd6809,

title = "Safety validation of sense and avoid algorithms using simulation and evolutionary search",

abstract = "We present a safety validation approach for Sense and Avoid (SAA) algorithms aboard Unmanned Aerial Vehicles (UAVs). We build multi-agent simulations to provide a test arena for UAVs with various SAA algorithms, in order to explore potential conflict situations. The simulation is configured by a series of parameters, which define a huge input space. Evolutionary search is used to explore the input space and to guide the simulation towards challenging situations, thus accelerating the process of finding hazards and supporting the validation process. We applied our approach to the recently published Selective Velocity Obstacles (SVO) algorithm. In our first experiment, we used both ran-dom and evolutionary search to find mid-air collisions where UAVs have perfect sensing ability. We found evolutionary search can find some hazards (here, interesting problems with SVO) that random search takes a long time to find. Our second experiment added sensor noise to the model. Random search found similar problems as it did in experiment one, but the evolutionary search found some interesting new problems. The two experiments show that the proposed approach has potential for safety validation of SAA algorithms",

author = "Xueyi Zou and Rob Alexander and McDermid, {John Alexander}",

year = "2014",

language = "English",

note = "33rd International Conference on Computer Safety, Reliability, and Security, SAFECOMP 2014 ; Conference date: 10-09-2014 Through 12-09-2014",

}

TY - CONF

T1 - Safety validation of sense and avoid algorithms using simulation and evolutionary search

AU - Zou, Xueyi

AU - Alexander, Rob

AU - McDermid, John Alexander

PY - 2014

Y1 - 2014

N2 - We present a safety validation approach for Sense and Avoid (SAA) algorithms aboard Unmanned Aerial Vehicles (UAVs). We build multi-agent simulations to provide a test arena for UAVs with various SAA algorithms, in order to explore potential conflict situations. The simulation is configured by a series of parameters, which define a huge input space. Evolutionary search is used to explore the input space and to guide the simulation towards challenging situations, thus accelerating the process of finding hazards and supporting the validation process. We applied our approach to the recently published Selective Velocity Obstacles (SVO) algorithm. In our first experiment, we used both ran-dom and evolutionary search to find mid-air collisions where UAVs have perfect sensing ability. We found evolutionary search can find some hazards (here, interesting problems with SVO) that random search takes a long time to find. Our second experiment added sensor noise to the model. Random search found similar problems as it did in experiment one, but the evolutionary search found some interesting new problems. The two experiments show that the proposed approach has potential for safety validation of SAA algorithms

AB - We present a safety validation approach for Sense and Avoid (SAA) algorithms aboard Unmanned Aerial Vehicles (UAVs). We build multi-agent simulations to provide a test arena for UAVs with various SAA algorithms, in order to explore potential conflict situations. The simulation is configured by a series of parameters, which define a huge input space. Evolutionary search is used to explore the input space and to guide the simulation towards challenging situations, thus accelerating the process of finding hazards and supporting the validation process. We applied our approach to the recently published Selective Velocity Obstacles (SVO) algorithm. In our first experiment, we used both ran-dom and evolutionary search to find mid-air collisions where UAVs have perfect sensing ability. We found evolutionary search can find some hazards (here, interesting problems with SVO) that random search takes a long time to find. Our second experiment added sensor noise to the model. Random search found similar problems as it did in experiment one, but the evolutionary search found some interesting new problems. The two experiments show that the proposed approach has potential for safety validation of SAA algorithms

M3 - Paper

T2 - 33rd International Conference on Computer Safety, Reliability, and Security, SAFECOMP 2014

Y2 - 10 September 2014 through 12 September 2014

ER -