[논문 리뷰] Learning Transferable Graph Exploration - 4.Experiments - (1)Synthetic 2D Maze Exploration

[논문 리뷰] Learning Transferable Graph Exploration - 0.Abstract

[논문 리뷰] Learning Transferable Graph Exploration - 1.Introduction

[논문 리뷰] Learning Transferable Graph Exploration - 2.Problem Formulation

[논문 리뷰] Learning Transferable Graph Exploration - 3.Model

[논문 리뷰] Learning Transferable Graph Exploration - 4.Experiments - (1)Synthetic 2D Maze Exploration

[논문 리뷰] Learning Transferable Graph Exploration - 4.Experiments - (2) Generating Inputs for Testing Domain Specific Programs

[논문 리뷰] Learning Transferable Graph Exploration - 4.Experiments - (3)App Testing

[논문 리뷰] Learning Transferable Graph Exploration - 5.Related work & 6.Conclusion

---

이번 섹션에서는,  2차원 미로에서 탐색 전략을 학습하는 효율성에 대해서 처음 설명하고, 본 논문에서 소개하는 모델이 프로그램을 위한 test case들을 생성하는 학습을 통해 프로그램 test의 문제를 study한다.

마지막으로 가상과 현실의 모바일 어플을 탐색하는 것을 통해 본 논문에서 소색하는 알고리즘을 평가한다.

최종적인 알고리즘을 $GMetaEXP$(Graph Meta-Exploration)이라 정의하여 사용했다.

더 자세한 설명은 Appendix B에 나와있다.

 

agent를 학습시기키 위해서, 동일한 분리된 세팅에서 advantage actor critic 알고리즘을 적용했다.

데이터 생성기를 통한 가상의 실험의 경우, 학습 graph environment을 즉시 생성한다.

inference를 하는 동안에, agent는 본 적 없는 graph에 배치되고, 그것의 parameter에 대한 fine-tuning을 할 수 없게 된다.(zero-shot generalization)

 

비교할 베이스라인은 다음 카테고리로 나뉜다.

• Random exploration: 각 step마다 action을 random하게 선택
• Heuristics: 전통적인 방법이 DFS(Depth-First-Search)
• Exact Solver: 프로그램을 test할 때 Z3와 비교한다. Z3는 SMT solver 부분에서 SOTA급이다. Z3는 충분한 계산시간이 주어지면 최적의 솔루션을 찾을 수 있다.
• Fuzzer: 프로그램 테스트를 위한 AFL과 Neuzz와 같은 SOTA급 fuzzing tool을 사용하여 비교했다.
• RL baselines: 서로 다른 history 정보 혹은 다른 history encoding model을 사용하는 강화학습 모델과도 비교했다.

 

 

4.1 Synthetic 2D Maze Exploration

간단한 탐색 실험으로 2차원 미로를 했다.

목적은 제한된 step 안에서 가능한 많은 미로 구석구석을 방문하는 것을 목표로 했다.

이것은 맵을 구축하는 것과 같이 agent가 environment를 탐색하는 것과 SLAM 등과 같은 것을 사용하여 map을 구축하는 것처럼 다른 적용에 적용할 수 있을 것으로 기대된다.

이번 셋업에서는, agent는 오직 현재 위치를 중심으로 주변의 작은 neighborhood만 관찰하고, 방문했던 곳의 2차원 좌표는 모르는 상태이다.

각 step때마다 상하좌우의 4가지 action만 가능하다.

 

더 구체적으로 말하자면, 아래의 규약을 따랐다.

• Observation: 관측된 $G_t$는 agent가 시간 $t$동안 미로를 가로지르는 부분에 대해, 현재의 위치에서 1-hop vision만큼 포함하여 위치(node를 의미)와 연결(edge를 의미) 추가한다.
• Reward: 식 (2)에서 정의한 것처럼, positive reward는 새로운 위치를 방문하였을때 받게된다.
• Termination: agent가 모든 노드를 돌았거나 정해진 탐색 예산인 $T$만큼을 다 소진했다면 종료된다.

random한 6 by 6의 미로를 학습하고, 같은 환경에서의 100 지정된 미로로 테스트를 진행했다.

starting point는 random하게 정해졌다.

agent가 $T = 36$ step만큼 움직일 수 있게 하였고, 100개의 지정된 미로를 커버하는 ~~

 

<table 2>는 본 논문에서 소개하는 방법과 baseline으로써의 random exploration을 정량화된 performance으로 보여준다.

베이스라인은 uniform random policy(이하 Random)과 agent가 backtrack하는 것을 허용하고 현재의 DFS stack에서 node를 맹목적으로 방문하는 것을 피하는 random next-step selection을 따르는 DFS policy(이하 RandDFS)가 있다.

탐색 action 순서가 고정된 것이 아닌 ramdom한 DFS와 같은 것들을 기억해야한다.

본 논문에서 소개하는 탐색 전략은 <그림 2>에서 보이는 각기 다른 접근방식처럼 확연히 더 좋게 수행한다.

 

본 논문에서는 graph 구조와 각기 다른 많은 history modeling 사용의 중요성에 대해 ablation study를 진행했다.(자세한 것은 appendix B.4)

그리고

1. full graph 구조를 exploiting하는 것은 현재의 node(33%)를 관측으로만 사용하는 것보다 상당히 좋은 결과를 내었다.
2. history를 아우르는 autoregressive aggregation은 마지막 step만 사용하는 것보다 월등히 좋은 결과를 내었다. 최고 performace는 single step observation을 사용하는 것과 비교하였을 때 full history를 modeling하는 것이 5%가량 성능 향상을 가져왔다.