Scheduling problem for persistent automated robotic service

Abstract

무인항공기와 같은 자동 로봇 차량의 운행 시간은 배터리 혹은 연료 용량에 의해 제한이 된다. 따라서, 무인항공기에 의해 수행가능한 임무 기간은 연료 충전 등의 보조 체계 없이는 제한이 된다. 그러나, 연료 서비스 스테이션등의 자동 지원 체계가 갖추어진 무인항공기의 시스템과 그것들을 아우르는 알고리즘일 활용한다면 오랜기간의 미션을 수행할 수 있다. 연료 수행으로 인하여 연료를 소모한 무인항공기는 새로운 무인항공기와 임무교대를 한다. 연료가 소모된 무인항공기는 근처의 지원 시설로 이동하여 연료를 충전한다. 이러한 지속 가능한 무인항공기 서비스를 지원하기 위하여 본 논문에서는 세 종류의 자동화 로봇을 위한 스케쥴링 문제 및 차량경로문제를 다룬다.

제 2장에서는 여러 개의 충전 기지가 존재하는 상황에서 복수의 무인항공기를 활용하여 이동하는 객체에 대한 감시 및 추적 서비스가 고려되었다. 이동하는 객체의 감시 및 추적 서비스는 이미 알려져 있는 것으로 가정되었으며, 무인항공기들은 최초에 충전 기지에 위치한다. 이러한 상황에서 수리적 모델을 통해 무인항공기의 운행 일정을 효율적으로 도출해 내었다. 제시된 수리적 모델의 복잡성을 해결하기 위하여 적은 수의 결정 변수를 지닌 새로운 수리적 모델 및 유전 알고리즘이 개발되었다.

제 3장에서는 2장에서 제시된 모델의 현실 적용을 위한 한계점이 해결되었다. 서비스의 운행 중 새로운 서비스의 요청, 예상 못했던 무인항공기의 손실, 급격한 연료 소모 등으로 인하여 새로운 운행 일정을 도출해야 할 상황이 발생 가능한데, 기존의 모델은 무인항공기가 최초에 충전 기지에 연료가 없는 상태로 존재한다는 가정사항이 존재하여 새로운 운행 일정 도출에 제약이 있었다. 따라서, 무인항공기들의 현재 위치 및 연료 상황, 남은 연료량에 반영된 충전 시간 등이 고려된 수리적 모델이 제시되었다. 지속적이고 신뢰성 있는 서비스의 제공을 위해 빠른 시간에 효율적인 운행 일정을 도출할 수 있는 순차적 임무 할당 알고리즘이 개발되었다.

제 4장에서는 위에서 제안된 수리적 모형이 일반화 된다. 즉, 복수의 차량들은 어느 기지에서나 충전 및 적재가 가능하다. 고객들은 이동 경로 혹은 고정된 위치 정보, 요구 수요, 서비스 시간, 우선수위 및 서비스 시작 시간에 대한 제약을 지니고 있으며, 차량들은 최초 위치, 연료 상황, 적재된 물품의 용량으로 정의된다. 이러한 상황에서 총 운행 거리의 합을 최소화시키며 수행된 임무들의 총 우선순위의 합을 최대화 시키기 위한 수리적 모델이 개발되었다. 개발된 모델의 최적해를 찾기 위하여 분기한정법이 개발되었다. 개발된 분기한정법은 상업적 소프트 웨어인 CPLEX보다 짧은 시간에 최적해를 찾을 수 있었다. 또한 더욱 짧은 시간에 효율적인 해를 찾기 위하여 3장에서 개발된 순차적 임무 할당 알고리즘이 4장에 맞게 일반화 되었다. 일반화된 순차적 임무 할당 알고리즘은 합리적인 해를 빠를 시간에 도출함으로써 실시간 서비스 운영을 위한 로봇 스케쥴링 도출에 적합한 알고리즘임이 증명되었다.

제 5장에서는 본 연구를 통하여 개발된 알고리즘의 성능 비교가 실행되었다. CPLEX, 분기한정법, 유전 알고리즘, 순차적 임무 할당 알고리즘, 일반화된 순차적 임무 할당 알고리즘이 2개의 예제를 통하여 성능 비교 및 원인 분석이 제공되었다.

본 연구에서 제시된 수리적 모형 및 해법 알고리즘들은 이동 경로를 포함한 복잡한 물류, 운송, 추적, 감시 임무 등을 수행하는데 있어서 효율적인 자동화 로봇의 운행 스케쥴을 합리적인 시간 안에 도출할 수 있다. 따라서, 자동화 로봇들을 통한 군사적, 물류 및 운송 임무들의 지속적이며 실시간적 운영에 크게 이바지 할 것으로 사료된다.