[논문]지속정찰 임무의 경로계획을 위한 불확실 기댓값 오리엔티어링 문제와 해법

김두영

doi:10.9766/kimst.2019.22.5.667

지속정찰 임무의 경로계획을 위한 불확실 기댓값 오리엔티어링 문제와 해법
Orienteering Problem with Unknown Stochastic Reward to Informative Path Planning for Persistent Monitoring and Its Solution 원문보기

韓國軍事科學技術學會誌 = Journal of the KIMST, v.22 no.5, 2019년, pp.667 - 673

김두영 (해군사관학교 컴퓨터과학과)

Abstract ▼ AI-Helper

We present an orienteering problem with unknown stochastic reward(OPUSR) model for persistent monitoring tasks with unknown event probabilities at each point of interest. Prior studies on orienteering problem for persistent monitoring task assume that rewards and event probabilities are known as a prior. In this paper, we propose a stochastic reward model with unknown event statistics and a path re-planning algorithm based on Bayesian reward inference. Experiments demonstrate the efficiency of our method.

주제어

표/그림 (5)

그림 Fig. 1. Concept of persistent monitoring tasks(black dot: base station, blue dots: high reward points, cells: points of interests)
표 Algorithm 1 Bayesian reward inference and path re-planning
그림 Fig. 2. Cumulated regrets in synthetic environments: (a) regrets at the 200-th sortie with varied T_max (b) regrets per sorties
그림 Fig. 3. Traffic accidents in Seoul(South Korea) from 2014 to 2016
그림 Fig. 4. Cumulated regrets in real world environments

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

따라서 본 문제에서는 매 소티 별 경로계획에 있어 불확실성 최소화를 위한 작전 영역의 탐사와 기대 이득 최대화를 위한 탐색 간의 비중을 조절하는 것이 전체 지속정찰 임무의 효과를 결정하는 중요한 요인이 된다.
추후 제안한 기법을 기반으로 한 근사 알고리즘 기반의 경로 재계획 기법을 통해 계산 복잡도 문제를 해결함으로써, 더욱 넓은 영역에서의 지속정찰 임무의 해를 구할 수 있는 연구를 진행하고자 한다. 또한, 확률 변수가 시간에 따라 변화하는 상황에서 정찰 임무 수행을 위한 샘플링 기법을 연구하고자 한다.
베이지안 보상 추정은, 과거의 소티에서의 관측 결과를 바탕으로 다음 소티에서 각 관측 지점을 새로 관측하였을 때 얻을 수 있는 보상의 기댓값(expectation)을 추정하기 위한 목적으로 설계되었다. 문제 해결에 앞서, 우리는 모든 v_i ∈V의 사건 발생 확률(event probability)은 i.
본 논문에서는 새로운 OP 모델링 방법인 Orienteering Problem with Unknown Stochastic Reward(OPUSR)를 제시하고자 한다. OPUSR은 기존 OP가 해결하고자 하는 기댓값을 최대화하는 순회 경로생성 문제에 있어, 각 관측장소에서 얻을 수 있는 기댓값의 사건 통계량을 모르는 문제를 모델링 하고자 하였다.
OP는 주어진 예산 제약 내에서 최대 이익(reward)을 얻을 수 있는 순회 경로(cyclic path)를 계획하는 문제를 모델링 한다. 본 논문에서는 이러한 OP 기법을 기반으로 하여 UAV의 지속정찰 경로계획 문제를 모델링 하고자 한다.
본 연구에서는 작전 영역에서의 기대 이득이 불확실한 상황에서 지속정찰을 수행하기 위한 모델링 기법인 OPUSR을 제시하였다. 또한, 지속정찰 임무에서 OPUSR의 순회 경로 해를 구하기 위한 톰슨 샘플링 기반의 베이지안 보상 추정 기법과 이를 바탕으로 한 경로 재계획 알고리즘을 제시하였다.
본 연구의 목적은 연료 제약이 있는 UAV가 다수의 비행 소티로 구성된 지속정찰 임무를 수행함에 있어 사건 R을 최대한 접촉할 수 있는 순회 경로(cyclic path) π를 생성하는 것이다.
본 장에서는 사건 발생확률 θ를 알 수 없는 환경에서 수행되는 지속정찰 임무를 모델링 하기 위한 OPUSR 기법을 제안한다.
지속정찰 임무(persistent monitoring task)는 주어진 작전 영역을 장시간 지속적으로 정찰하여 작전 영역 안에서 발생하는 다양한 확률 사건을 관측하는 것을 목적으로 한다.^[1] 이는 과거의 보병, 정찰 차량, 초계기, 함정 등의 유인 플랫폼을 활용하여 일정 시간 간격으로 작전 영역을 정찰함으로써 적 부대의 이동, 공격 징후 등을 감지하는 형태로 수행되어 왔다.

가설 설정

각 관측 지점의 사건 발생확률 θi는 해당 지역에서 발생한 실제 교통사고의 수를 기준으로 [0.2, 0.8]을 기준으로 표준화하여 설정하였으며, UAV는 사전에 이 θi를 알지 못한다고 가정하였다.
문제 해결에 앞서, 우리는 모든 vi ∈V의 사건 발생 확률(event probability)은 i.i.d이며 정적(stationary)[1]이라고 가정한다.
우리는 각 vi에서의 event statistic θi는 알 수 없으며 모든 θi ∈θ는 각각 상호 독립임을 가정한다.
이때, v₁과 v_N은 각각 시작점과 끝점을 의미하며, 위치는 동일하다고 가정한다. 이 좌표는 UAV의 비행장 위치를 의미한다.
은 관측영역 내 모든 관측 지점(Point Of Interest : POI)의 관측 기댓값이 정규분포를 따를 때, 기댓값을 최대화하는 문제를 모델링 하기 위한 Orienteering Problem with Stochastic Profit(OPSP)를 제시하였다^[3]. 이때, 기댓값의 사건 통계량(event statistic)인 평균과 분산은 이미 알고 있다고 가정하였다.

제안 방법

본 논문에서는 새로운 OP 모델링 방법인 Orienteering Problem with Unknown Stochastic Reward(OPUSR)를 제시하고자 한다. OPUSR은 기존 OP가 해결하고자 하는 기댓값을 최대화하는 순회 경로생성 문제에 있어, 각 관측장소에서 얻을 수 있는 기댓값의 사건 통계량을 모르는 문제를 모델링 하고자 하였다.
먼저 작전 영역 내 각 관측 지점의 사건 기댓값을 임의로 생성한 환경에서의 지속정찰을 위한 경로생성 실험을 수행하였다. 또한, 실제 환경에서의 적용 가능성을 확인하기 위하여 대한민국의 서울시에서 발생한 교통사고의 위치정보를 활용하여 관측 환경을 구성하고, 해당 영역 내에서 최대한 많은 수의 교통사고를 관측하기 위한 경로를 생성하는 실험을 수행하였다.
본 연구에서는 작전 영역에서의 기대 이득이 불확실한 상황에서 지속정찰을 수행하기 위한 모델링 기법인 OPUSR을 제시하였다. 또한, 지속정찰 임무에서 OPUSR의 순회 경로 해를 구하기 위한 톰슨 샘플링 기반의 베이지안 보상 추정 기법과 이를 바탕으로 한 경로 재계획 알고리즘을 제시하였다.
먼저 2014년부터 2016년까지 대한민국 서울에서 발생한 교통사고 데이터의 경위도 좌표를 분석하여 Fig. 3과 같이 도식화하였다^[7].
제시된 모델링 기법과 기댓값 추정 기법의 성능을 검증하기 위하여 UAV를 활용한 두 가지 테스트를 수행하였다. 먼저 작전 영역 내 각 관측 지점의 사건 기댓값을 임의로 생성한 환경에서의 지속정찰을 위한 경로생성 실험을 수행하였다. 또한, 실제 환경에서의 적용 가능성을 확인하기 위하여 대한민국의 서울시에서 발생한 교통사고의 위치정보를 활용하여 관측 환경을 구성하고, 해당 영역 내에서 최대한 많은 수의 교통사고를 관측하기 위한 경로를 생성하는 실험을 수행하였다.
먼저, 우리의 알고리즘을 임의로 생성된 환경에서 테스트하였다. 작전 구역을 4 × 4의 구역으로 분할, 총 16개의 관측 지점을 설정하였다.
본 장에서는 지속정찰 임무의 효과적 경로생성을 위한 베이지안 보상 추정(Bayesian reward inference) 기법과, 이를 바탕으로 한 경로 재생성 알고리즘(Path re-planning algorithm)을 제안한다.
위를 바탕으로 결정된 지속정찰의 순회 정찰 경로는 정찰이 진행될 때마다 정보의 불확실성이 감소하여 최적의 경로로 재계획된다. 알고리즘 1은 베이지안 보상 추정 기법과 결합한 경로 재계획 방법을 기술한다.
Ilhan et al.은 관측영역 내 모든 관측 지점(Point Of Interest : POI)의 관측 기댓값이 정규분포를 따를 때, 기댓값을 최대화하는 문제를 모델링 하기 위한 Orienteering Problem with Stochastic Profit(OPSP)를 제시하였다^[3]. 이때, 기댓값의 사건 통계량(event statistic)인 평균과 분산은 이미 알고 있다고 가정하였다.
2(b)는 관측 임무의 진행에 따른 누적 손실 값의 변화를 나타낸다. 이 실험에서 우리는 T_max값을 7로 고정한 상태로 1,000회의 실험한 이후 그 평균을 기록하였다. 그림에서 ∊-greedy와 UCB-1의 누적 손실 값은 임무가 수행됨에 따라 지속해서 증가하는 모습을 보여준다.
이 실험에서 우리는 총 100개의 환경을 임의로 생 성하였고, 환경별 누적 손실 값들의 평균을 측정하였다. 이를 통하여 최대 비행 가능 거리에 따른 알고리 즘의 성능을 비교하였다.
이와 더불어 OPUSR 모델링 기법을 활용하여 불확실 영역에서의 지속정찰을 위한 경로계획 문제를 해결하기 위하여 베이지안 보상 추정 및 경로 재계획 기법을 제시하였다. OPUSR에서 최적화된 경로를 계획하기 위해서는 작전 영역의 사건 통계량 추정을 위한 다수의 탐사(exploration)가 필요하다.
작전 영역과 관측 지점을 구성하기 위하여 서울시 전역을 5 × 5 크기의 그리드로 나누어, 총 25개의 관측 지점을 설정하였고, 각각의 관측 지점을 노드의 집 합 V로 하였으며, Tmax 값은 14로 정하였다.
그러나 사건 통계량의 불확실성 감소를 위해 탐사에 집중할 경우 사건의 관측 기회를 증가시키는 탐색(exploit)에 소홀하게 되어 전체 기댓값이 감소하게 되는 딜레마에 빠지게 된다^[5]. 제시된 기법은 매 소티에서 기댓값을 최대화하기 위한 경로를 계획함에 있어, 과거 소티의 관측정보를 바탕으로 각 관측 지점의 관측 확률을 베이지안 샘플링 기법으로 제시함으로써, 관측 지점의 사건 통계량 추정을 위해 손실되는 불필요한 소티를 최소화하는 기법을 제시한다.
제시된 모델링 기법과 기댓값 추정 기법의 성능을 검증하기 위하여 UAV를 활용한 두 가지 테스트를 수행하였다. 먼저 작전 영역 내 각 관측 지점의 사건 기댓값을 임의로 생성한 환경에서의 지속정찰을 위한 경로생성 실험을 수행하였다.
이와는 대조적으로, 제안한 알고리즘은 이러한 탐사 변수 기반의 기법을 사용하지 않는다. 제안된 베이지 안 기반의 알고리즘은 과거 관찰 결과에 기반한 베타 분포를 통하여 추출한 기대 이득을 바탕으로 탐색의 우선순위를 결정한다. 초기 관측 소티에서는 작전 영역에 대한 불확실성이 높으므로, 베타분포의 특성에 따라 추출된 기대 이득이 전 작전 영역에 비슷한 값 으로 분포하게 된다.
제안한 기법의 성능을 실제 환경 발생한 데이터를 기반으로 검증하기 위하여 도시에서 발생하는 교통사고를 UAV를 통해 감지하는 시나리오를 테스트하였다.
제안한 베이지안 기반의 경로계획 알고리즘의 성능을 검증하기 위해, 우리는 임의값을 기반으로 한 환경과, 실제 교통사고 데이터를 기반으로 한 환경에서 테스트를 수행하였다. 성능 검증의 비교 대상으로 MLE 방식의 탐색 기법인 ∊-greedy, UCB-1을 사용하였다.

대상 데이터

8]을 기준으로 표준화하여 설정하였으며, UAV는 사전에 이 θ_i를 알지 못한다고 가정하였다. UAV의 모기지는 김포공항의 좌표가 위치한 노드로 설정하였다. 기대 손실은 총 100번의 실험 결과의 평균값으로 측정하였다.

데이터처리

UAV의 모기지는 김포공항의 좌표가 위치한 노드로 설정하였다. 기대 손실은 총 100번의 실험 결과의 평균값으로 측정하였다.
이 실험에서 우리는 총 100개의 환경을 임의로 생 성하였고, 환경별 누적 손실 값들의 평균을 측정하였다. 이를 통하여 최대 비행 가능 거리에 따른 알고리 즘의 성능을 비교하였다.

이론/모형

. 본 논문에서는 제안한 베이지안 추정 기법의 성능 측정을 위해 정수 계획법(Integer Programming Solver : IPSolver)를 사용하여 정확한 해를 구하였다.
제안한 베이지안 기반의 경로계획 알고리즘의 성능을 검증하기 위해, 우리는 임의값을 기반으로 한 환경과, 실제 교통사고 데이터를 기반으로 한 환경에서 테스트를 수행하였다. 성능 검증의 비교 대상으로 MLE 방식의 탐색 기법인 ∊-greedy, UCB-1을 사용하였다. 모든 실험에서 ∊-greedy 알고리즘의 ∊ 값은 0.

성능/효과

임의로 구성된 환경과, 실제 교통사고 데이터를 기반으로 한 환경에서의 검증 실험에서, 제안한 보상 추정 기법은 기존의 MLE 기반 보상 추정 기법 대비 최소한의 이익 손실로 장기적인 지속정찰 임무를 수행하는 결과를 보여주었다.

후속연구

추후 제안한 기법을 기반으로 한 근사 알고리즘 기반의 경로 재계획 기법을 통해 계산 복잡도 문제를 해결함으로써, 더욱 넓은 영역에서의 지속정찰 임무의 해를 구할 수 있는 연구를 진행하고자 한다. 또한, 확률 변수가 시간에 따라 변화하는 상황에서 정찰 임무 수행을 위한 샘플링 기법을 연구하고자 한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	무인 항공기가 군사 목적으로 사용되는 이유는?	최근 무인 항공기(UAV), 무인수상정(USV)등의 무인 플랫폼과 인공지능 기반의 자율주행 기술의 발달은 기존의 유인 정찰 수단을 이용하는 방법에 대비하여 지속정찰 임무의 임무 용이성을 증대시킴에 따라, 이러한 지속정찰 임무의 적용 범위가 화재 감시, 기상이변, 재난 대응 등 비군사 목적의 정찰 및 감시로 확대 되고 있다. 특히, 무인 항공기(Unmanned Aerial Vehicle : UAV)는 넓은 전장 환경을 빠른 속도로 정찰할 수 있으며, 인원 손실의 위험이 적어서 군사 목적의 다양한 정찰 임무에 사용되고 있다.
	지속정찰 임무의 목적은?	지속정찰 임무(persistent monitoring task)는 주어진 작전 영역을 장시간 지속적으로 정찰하여 작전 영역 안에서 발생하는 다양한 확률 사건을 관측하는 것을 목적으로 한다. [1] 이는 과거의 보병, 정찰 차량, 초계기, 함정 등의 유인 플랫폼을 활용하여 일정 시간 간 격으로 작전 영역을 정찰함으로써 적 부대의 이동, 공격 징후 등을 감지하는 형태로 수행되어 왔다.
	생성된 탐색 경로가 Tmax를 초과하지 않는다는 의미는?	네 번째 제약조건은 생성된 탐색 경로가 연료에 따른 이동 거리 제약조건 Tmax를 초과하지 않도록 한다. 즉 연료가 다 소진되기 전에 반드시 모기 지로 복귀해야 함을 의미한다. 마지막 제약조건은 생 성된 경로 Ts에서 sub-tour가 발생하는 것을 방지한다.

참고문헌 (7)

Yu, J. Schwager, M. and Rus, D., "Correlated Orienteering Problem and its Application to Informative Path Planning for Persistent Monitoring Tasks," IEEE Conf. on Intelligent Robots and Systems(IROS), Chicago, Illinois, pp. 342-349, Sept. 2014.
Vansteenwegen, P. Souffriau, W. and Van Oudheusden, D., "The Orienteering Problem: A Survey," European Journal of Operational Research, 209(1):, pp. 1-10, 2011.

상세보기
Ilhan, T. Iravani, S. M. and Daskin, M. S., "The Orienteering Problem with Stochastic Profits," Iie Trans., 40(4), pp. 406-421, 2008.

상세보기
Baykal, C. Rosman, G. Claici, S. and Rus, D., "Persistent Surveillance of Events with Unknown, Time-Varying Statistics," IEEE Conf. on Robotics and Automation(ICRA), pp. 2682-2689, May 2017.
Sutton, R. S. and Barto, A. G., "Reinforcement Learning: An Introduction," MIT Press, Cambridge, 1998.
Thompson, W. R., "On the Likelihood That One Unknown Probability Exceeds Another in View of the Evidence of Two Samples," Biometrika, 25(3/4), pp. 285-294, 1933.
Republic of Korea Government Open Data Portal, "Traffic Accident Information," http://data.go.kr/dataset/15003493/fileData.do, accessed March, 2019.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증