Поиск путей для группы автономных транспортных средств при исследовании неизвестной территорий

Abstract

Представлен алгоритм исследования заранее неизвестной территории с помощью группы автономных транспортных средств (АТС). В нем используется новый метод выбора точек назначения для каждого АТС из группы. Новизна данного метода заключается в использовании кластеризации граничной области – области карты препятствий, находящейся на границе ее исследованной части. Каждому АТС сопоставляется некоторый кластер с помощью поиска паросочетания минимального веса. Точка назначения выбирается из кластера с помощью функции приоритета – функции, определяющей выгодность выбора клетки в зависимости от затрат на ее достижение, количества полученной информации и расстояния до целей других АТС.

In this paper, a path planning algorithm for multi-robot exploration is presented. It is developed for exploration in initially unknown areas. The algorithm is based on a novel method of choosing exploration targets. This method uses clusterization of frontier space – part of explored map space which is situated on its border with an unexplored part. Every robot is being associated with a cluster. Then the exploration target for the robot is chosen from associated cluster with a priority function. This function defines utility for choosing a map cell considering traverse cost, information gain and distance to other robots' targets.