Развитие современных технологий приводит к все большей автоматизации процессов, выполняемых человеком в различных сферах жизнедеятельности, таких как медицина, образование, сельскохозяйственное, промышленное и военное дело. В настоящее время имеется множество устройств, способных заменить людей в опасных или труднодостижимых для человека местах, ускорить и облегчить выполнение различных задач.
На данный момент актуальной темой является создание автоматизированных технологических систем, реализующих групповое взаимодействие агентов для выполнения общей задачи. Например, построение карты местности, поисково-спасательные операции, орошение полей,
тушение пожара, обеспечение эффективного слежения группой беспилотников за стратегически важными объектами, и т.д. Такие задачи могут быть сведены к задаче о покрытии поля. Поле — это плоскость с заданной декартовой системой координат, состоящая из клеток, каждая из которых представляет собой одну квадратную единицу. В задаче о покрытии поля группа агентов должна полностью его покрыть, а именно посетить все клетки поля.
Для эффективного выполнения задачи покрытия поля несколькими агентами необходимо разделить между ними поле, т.к. оно может оказаться существенно больше, чем количество агентов. Такое разбиение можно построить с помощью разбиения Вороного, или диаграммы Вороного [9]. Достоинством метода разбиения Вороного является учет начального положения агентов (т.к агенты являются точками, для которых строится диаграмма Вороного), получение непересекающихся областей, представляющих собой выпуклые многоугольники, а также возможность реализации данного метода разного рода модификациями алгоритмов с различными требованиями к ресурсам. Таким образом, для решения задачи о покрытии поля, мы можем поручить построение разбиения любому из агентов, сделав полученное разбиение доступным оставшимся участникам.
Для обмена информацией между агентами и обеспечения ее согласованности удобно использовать операционную систему реального времени (ОСРВ) с поддержкой распределенной памяти. В данной работе используется ОСРВ МАКС [15], которая может быть применена для создания систем, включающих несколько интеллектуальных узлов — аппаратных средств, общающихся между собой. ОСРВ МАКС предназначена для систем реального времени и других встраиваемых систем под управлением ARM микроконтроллеров на базе 32-битных ядер Cortex-M3, Cortex-M4, Cortex-M4F с RISC архитектурой. В данной ОСРВ предложена модель общей распределенной памяти (distributed shared memory, DSM) — DSM МАКС [13], которая обеспечивает каждого агента системы доступом к общей памяти, возможностью писать и читать данные.
Таким образом, данная работа посвящена реализации разбиения поля с помощью разбиения Вороного для ОСРВ МАКС.
Таким образом, в рамках данной работы получены следующие результаты.
1. Изучены алгоритмы Форчуна, Инкрементальный и «Разделяй и властвуй», позволяющие реализовать разбиение поля между объектами. Рассмотрены библиотеки, реализующие разбиение Вороного алгоритмом Форчуна.
2. Реализован алгоритм Форчуна при помощи библиотеки Boost.Polygon Voronoi. Разработан метод, позволяющий по построенной диаграмме, достроить разбиение Вороного полностью.
3. Реализован инкрементальный алгоритм с использованием структуры данных DCEL.
4. Произведены апробация в ОСРВ МАКС и сравнение работы алгоритмов Форчуна и инкрементального. В ходе сравнения было выявлено, что реализованный инкрементальный алгоритм со структурой данных DCEL по времени работает быстрее, чем дополненный функциональностью алгоритм Форчуна библиотеки Boost.Polygon Voronoi.
5. Тезисы доклада с основными результатами работы опубликованы в сборнике конференции ”Современные технологии в теории и практике программирования” [10].
6. Представлен доклад на конференции SYRCoSE-2018.
7. Программная разработка расположена на веб-сервисе для хостинга IT-проектов GitHub https://github.com/ivm23/Voronoi
