Доклады Российской академии наук. Науки о Земле, 2021, T. 501, № 2, стр. 210-218

Использование алгоритмов искусственного интеллекта для оптимального планирования морских сейсмических работ

С. В. Зайцев 12*, Член-корреспондент РАН С. А. Тихоцкий 23, С. В. Силаев 1, А. А. Ананьев 1, Р. В. Орлов 1, Д. Н. Ужегов 1, И. Ю. Кудряшев 12, Б. В. Васекин 12, С. И. Кондрашенко 12, С. О. Базилевич 4

1 ООО “Инжиниринговый центр МФТИ по полезным ископаемым”
Москва, Россия

2 Московский физико-технический институт (Национальный исследовательский университет)
Москва, Россия

3 Институт физики Земли им. О.Ю. Шмидта Российской академии наук
Москва, Россия

4 АО “МАГЭ”
Москва, Россия

* E-mail: zaycev.sv@cet-mipt.ru

Поступила в редакцию 03.09.2021
После доработки 09.09.2021
Принята к публикации 12.09.2021

Полный текст (PDF)

Аннотация

В работе представлен алгоритм, позволяющий оптимизировать стоимость и время выполнения морских сейсморазведочных исследований. Для решения задачи оптимального планирования предлагается применение эвристического алгоритма решения задачи коммивояжера на серии графов, к которой сводится система наблюдений сейсморазведки. Рассмотренный алгоритм предполагает работу с буксируемым оборудованием и с применением донных станций. Алгоритм обеспечивает близкий к минимальному путь, учет реальной геометрии судов и их скорости прохождения различных участков. Научная новизна работы заключается в применении генетического алгоритма оптимального планирования с учетом закрытия зон работ к задачам морской геофизики. Применение методов искусственного интеллекта позволило впервые в мировой практике разработать систему планирования, обеспечивающую возможность оперативной корректировки планов работ в зависимости от меняющихся метео- и иных условий, в том числе – при работе несколькими судами с использованием донных станций. В работе приведены описание разработанной методики, результаты разработки алгоритма в виде прикладного программного обеспечения и примеры планирования на тестовых данных.

Ключевые слова: морская сейсморазведка, планирование сейсмических исследований, транзитная зона, оптимальное планирование, искусственный интеллект, алгоритмы оптимизации, путь Дубинса, генетический алгоритм

ВВЕДЕНИЕ

Морские сейсмические исследования в условиях арктического шельфа и короткого периода навигации требуют от сервисных компаний максимальной оптимизации времени выполнения работ. Насущность данной проблемы обусловлена отсутствием доступной системы, позволяющей осуществлять гибкое планирование работ и адаптацию методики проведения морских сейсморазведочных работ в зависимости от складывающихся метеорологических условий и ледовой обстановки. В настоящее время большинство решений о смене плана работ непосредственно в полевых условиях принимаются экспертами на основе их субъективного опыта. Это зачастую приводит к игнорированию актуальной сложившейся обстановки и сохранению заранее утвержденного плана съемки, что влечет за собой увеличение операционных затрат.

Актуальность данной проблематики подтверждается обсуждениями в научных статьях [13]. Но в большинстве своем алгоритмы оптимизации затрагивают лишь часть процесса морской сейсмической съемки, как например, оптимизация времени циркуляций и перехода между профилями при проведении морских сейсмических 3D-работ и часто связаны с методикой работы с буксируемым оборудованием.

Все больше иностранных компаний (ION, Shlumberger, SurvOPT), специализирующихся на разработке коммерческого программного обеспечения по планированию работ, добавляют к своему функционалу оптимизацию движения судов. Однако санкционная политика в отношении российских нефтяных и сервисных компаний ставит порой непреодолимые барьеры на пути свободного использования зарубежного программного обеспечения. В связи с этим актуальна разработка отечественных систем поддержки принятия решений при проведении морских сейсморазведочных работ. Кроме того, имеющиеся зарубежные продукты не лишены недостатков, имеют ограниченный функционал, не отвечающий актуальным потребностям компаний, прежде всего – ведущих сейсморазведку в транзитной зоне.

В данной работе демонстрируются результаты разработки алгоритма планирования проведения морских сейсморазведочных работ на базе эвристических алгоритмов решения задачи коммивояжера (в англ. – Traveling salesman problem) для методики работ с донными станциями в транзитной зоне и буксируемой установкой. Предлагаемый алгоритм предоставляет пользователю полный методологический набор параметров для выбранной методики съемки с расчетом оптимального количества судов при работе в транзитной зоне (судов-раскладчиков и судов-источников) и необходимого донного оборудования для работ в транзитных зонах и на акватории. На базе разработанных алгоритмов создано прикладное программное обеспечение, которое вошло в состав программно-аппаратного комплекса.

ПОСТАНОВКА ЗАДАЧИ

Задача планирования заключается в построении оптимального, с точки зрения стоимости, маршрута прохождения профилей. Важно, что в морской сейсморазведке существуют две принципиально различные методики съемки (рис. 1): с применением буксируемого оборудования и с использованием донных станций в транзитной зоне с множеством судов (раскладчики оборудования и суда-источники сигнала).

Рис. 1.

Схематично изображение оборудования, используемого при морской сейсмической съемке.

Общим подходом для различной методики морской съемки является сведение задачи построения оптимального маршрута к решению задачи коммивояжера (Travel salesman problem, далее – TSP). Задача имеет множество применений при построении оптимальных маршрутов для логистики в разных сферах транспорта. Рассматриваемые модификации включают в себя как работу с буксируемым оборудованием, когда источник и приемник буксируются одним судном, так и с использованием донных станций, когда несколько судов-раскладчиков выкладывают на дно регистрационные станции, а судно-источник проходит по отдельным профилям для генерации сигнала.

Задача по прокладке маршрута формулируется следующим образом: имея набор из N отрезков на плоскости (профили сейсмических наблюдений), необходимо построить маршрут наименьшей длины (LoptL, где L – множество всех маршрутов) и требующий минимального времени работы. При этом в случае судна-источника каждый из отрезков должен быть пройден ровно один раз, а в случае судов-раскладчиков профили проходятся дважды: для раскладки донных станций и их сбора. Кроме того, необходимо учитывать технические ограничения (различные скорости судов при работе и движении между профилями, минимальный радиус разворота, число используемых станций каждым из судов-раскладчиков), статические запрещенные зоны (суша/мелководье) и динамические запрещенные зоны (ограничения ПРИП, погодные условия). Задачу необходимо решать с учетом одновременной работы в зоне нескольких судов одновременно (будем обозначать их количество m).

Оптимизация прохождения сети профилей морской сейсморазведки сводится к построению набора графов G(V, E), которые имеют следующие особенности:

1) вершинами графа (V) являются начала и концы профилей;

2) ребрами графа (E) являются сами траектории прохождения профиля;

3) вес ребра Ei (i = 1…N) определяется скоростью прохождения судна по профилю;

4) дополнительная стоимость (вес) определяется скоростью судна при выполнении разворота между профилями, при переходе между профилями;

5) при заходе на профиль судно должно пройти его до конца, т.е. если определена вершина входа, то определена вершина выхода;

6) Переход между вершинами графа ограничен минимальным радиусом кривизны разворота каждого отдельно взятого судна (Rmin).

Решение задачи с методикой буксируемого оборудования предполагает, что источник сигнала и кабель с приемниками вынесены за борт судна, что увеличивает его радиус разворота Rmin. Дополнительно для корректного построения оптимального маршрута определяются скорости m судов при работе (Vwork), развороте (Vturn), круизная (Vtarvel), т.е. скорость при движении между профилями, длина буксируемого оборудования, процент от длины оборудования, необходимый для захода на профиль и выхода из него.

Дополнительно учитываются зоны мелководья и береговой линии, как запрещенные к проходу в них статические области, и динамически меняющиеся во времени области временных запретов государственными службами, либо плохой погоды, которые накладывают ограничение на расписание прохождения отдельных профилей.

Из постановки следует, что задача оптимизации сводится к двум: оптимизации движения судна с выносным оборудованием по множеству графов Gi(V, E) (i = 1…N) с учетом погодных условий и статических препятствий, а также задаче оптимизации расписания укладчиков и движения судна-генератора.

АЛГОРИТМИЧЕСКАЯ БАЗА

Рассмотрим базовые (т.е. применяемые к двум методикам съемки) алгоритмы решения поставленной задачи. Предлагается использование алгоритма решения задачи TSP, который не требует обучении модели и дает возможность учитывать цену перехода между графами. Одним из наиболее успешных подобных алгоритмов для данной задачи является генетический [46].

Генетический алгоритм – эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора “скрещивания”, который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Основными понятиями в генетических алгоритмах являются популяция, особь и генотип. Генотип представляет собой вектор параметров, полностью определяющий частное решение задачи (не обязательно оптимальное). Генотип является свойством особи, которая также характеризуется числовым параметром, вычисляемым по генотипу, называемым функция приспособленности. Функция приспособленности – это та метрика, которая позволяет численно сравнить два частных решения.

Популяция представляет собой множество особей. Процессу оптимизации соответствует эволюция популяции – итерационный процесс смены поколений при наличии эволюционного давления, направленного на выживаемость особей с более высоким значением функции приспособленности.

В случае поиска оптимального пути для решения задачи оптимизации временных затрат роль данной метрики играет величина, обратная максимальному по всем кораблям времен прохождения маршрута (1):

(1)
$f = \frac{1}{{\mathop {\max }\limits_{i = 1 \ldots m} ti}},$
где m – количество судов, t – время прохождения i-м судном своего маршрута, т.е. набора графов Gi(V, E) (i = 1…N).

Применительно к задаче оптимизации морской съемки, особь – маршрут LiL прохождения профилей съемки со временем ti. Популяция – набор всех маршрутов (подмножество множества L). Генотип – последовательность прохождения набора графов Gi(V, E) (i = 1…N), т.е. маршрута съемки.

Детали процесса смены поколений могут сильно различаться и зависят от конкретной решаемой задачи. Опишем здесь тот вариант, который был использован нами для решения рассматриваемой задачи.

а) Вычисление функции приспособленности f для всей популяции L, сортировка особей в популяции по ее значению f.

б) Отбор из популяции 20% наиболее приспособленных особей Li, которые переходят в следующее поколение.

в) Генерация оставшихся 80% производится путем селекции: методом рулетки из старой популяции случайно выбираются двое родителей (L1, L2L) с вероятностью, пропорциональной их функции приспособленности f. С помощью кроссинговера генотипы родителей объединяются в генотип потомка, потомок добавляется к новому поколению.

г) К генотипам всех особей (кроме одной, наиболее приспособленной) с вероятностью в 20% применяется оператор мутации.

Используемый геном состоит из трех частей: первая часть представляет собой набор номеров Gi(V, E) (i = 1…N), переставленных в соответствии с порядком обхода для всех m-судов; вторая часть содержит набор бинарных значений, указывающих направление прохождения графа Gi, в котором проходится соответствующий граф (от первого узла V ко второму, либо наоборот); третья часть задает разбиение первой части на подмаршруты для каждого из судов: каждый элемент в нем ${{s}_{i}}$ – это индекс первого элемента в первой части генома, относящийся к маршруту судна i, а последний элемент равен общему числу треков.

Пример маршрута с соответствующим ему геномом представлен на рис. 2. Схематично изображение оборудования, используемого при морской сейсмической съемке.

Рис. 2.

Пример маршрута для двух судов и соответствующий ему геном.

Первоначальная популяция L генерируется случайным образом кроме одной особи, генотип которой строится по маршруту, задаваемому алгоритмом ближайшего соседа (nearest neighbor), который равномерно поделен между всеми m судами.

Наиболее подходящим для решения поставленной задачи является оператор кроссинговера, представленный в статье [8]. Данный метод позволяет совместить в одном алгоритме обмен генетической информацией как в части порядка и направления обхода треков, так и в части распределения треков между судами. Кратко его можно описать следующим образом:

1) Из генома родителя L1 для каждого из подмаршрутов выбираются непрерывные последовательности случайной длины (не превышающей длину подмаршрута соответствующего судна). Эти последовательности образуют начальные участки маршрутов судов у потомка.

2) Оставшиеся невыбранными треки упорядочиваются в соответствии с генотипом родителя L2.

3) Упорядоченный остаток из этапа 2 разбивается на m частей случайной длины.

4) Части из этапа 3 формируют остаток маршрута, полученного на этапе 1 для всех судов.

В качестве оператора мутации предлагается использование 2-opt, являющегося локальным эвристическим алгоритмом для решения TSP [9]. Пример работы алгоритма представлен на рис. 3. для сети графов.

Рис. 3.

Результат одной итерации алгоритма 2-opt: замена связей (be, cf) на (dc, ef) и инверсия заключенного между ними участка (edc).

Суть метода заключается в рассмотрении всех возможных пар связей в графе (ab, cd) и заменой их на (ac, bd), если это дает выигрыш по длине пути. Мутация части генома, отвечающей за распределение треков между судами, заключается в случайном сдвиге границ подмаршрутов с фиксированной вероятностью.

Важным моментом является то, что морское сейсмическое судно не может развернуться на месте без риска потерять или повредить буксируемое оборудование, поэтому нужно учитывать реальную геометрию судна при переходе с одного профиля на другой, а именно минимальный радиус разворота Rmin. Для этого был выбран алгоритм построения кратчайшего пути между вершинами графа Vi (i = 1…2N) с применением путей Дубинса [10]. Путь Дубинса – это кратчайшая кривая, которая соединяет две вершины графа Vi, j с учетом ограничения на радиус кривизны Rmin. Использование путей Дубинса используется для планирования движения транспортных средств с ограничением геометрии на движение средства [1, 11]. Радиус зависит от типа судна и размеров выносного оборудования рис. 4.

Рис. 4.

Пример построения траектории перехода суда с профиля на профиль с применением траекторий Дубинса: пунктиром обозначена окружность с радиусом Rmin.

Траектория прохождения маршрутов строится после выбора оптимального LoptL, когда становятся известна последовательность прохождения графов Gi(V, E) (i = 1…N). Последовательные вершины Vi и Vj графа, принадлежащие оптимальному генотипу Lopt, соединяются между собой кривыми Дубинса. Пример использования траектории прохода между профилями и запретной зоны (мелководье) с использованием путей Дубинса представлен на рис. 5.

Рис. 5.

Положение сейсмических профилей без статической запретной зоны (слева) и с включением запретной зоны (справа), в нижнем ряду – соответствующие оптимальные траектории Дубинса.

Одной из особенностей проведения работ в морских условиях является резкое изменение погоды. Шторм или сильное волнение могут нарушить планы проведения работ. Для их учета используется система автоматизированного получения прогноза погоды SailDocs. В алгоритме планирования зоны, закрытые для работ на определенное время, фигурируют как временные окна и накладывают необходимость в учете их при построении маршрута прохождения судна.

Статические зоны мелководья или нормативных ограничений на море (административные запреты, рыболовство, скважины) вносятся как запрещенные для движения области. Для корректного учета в алгоритме оптимального планирования множество графов Gi(V, E) (i = 1…N), на которые попадают закрытые зоны, разбивается на дополнительное подмножество: профили делятся пропорционально закрытой зоне. Вокруг закрытой зоны формируется буферная область размером 2*$\mathop {\max }\limits_m ({{R}_{{{\text{min}}}}})$ корректного учету радиуса разворота. Профили, попадающие на буферную зону, – обрезаются.

БУКСИРУЕМАЯ УСТАНОВКА

Первоначально рассмотрим реализованную последовательность оптимизации методики съемки для буксируемой установки, т.к. она наиболее показательна и является базовым алгоритмом для работы с донными станциями. По шагам алгоритма:

1) задание начальной точки выхода судна;

2) определение параметров судна: скорости, радиус разворота и т.д.;

3) загрузка погоды, создание временных зон на ее основе;

4) создание (опционально) статических зон; обрезка профилей, согласно созданным зонам закрытия;

5) построение оптимального маршрута с учетом зон закрытия:

а) формирование оптимального маршрута прохождения профилей генетическим алгоритмом;

б) учет временных зон: если судно проходит граф Gi в то время, когда он закрыт, происходит откат на шаг назад в формировании оптимального маршрута и исключение профиля из планирования на следующий шаг;

в) построение маршрута для судна с учетом статических зон, которые проходятся по кривым Дубинса так, чтобы судно не заходило в них при движении и маневре (развороте, переходе между профилями);

г) создание расписания оптимального по критерию стоимости;

д) проверка расписания: если судно заходит на профиль, попадающий во временную зону, то производится перестроение маршрута с учетом того, что профиль закрыт в определенное временное окно.

Для сравнения работы алгоритма были выбраны открытые данные морских сейсморазведочных работ в Мексиканском заливе [1512], с доступными навигационными файлами. Пример работы алгоритма построения оптимального маршрута для буксируемой установки в экспериментальном образце представлен на рис. 6.

Рис. 6.

Окно графического интерфейса с выводом решения задачи оптимизации для открытых данных USGS: красное – траектория из навигационных данных USGS, синяя – оптимизированный маршрут.

Продолжительность работы по данным USGS составила 30 дней и судно прошло 1265 км, тогда как генетический алгоритм предложил оптимальный план работ, занимающий 23 дня, с общей длиной маршрута 992 км. По приведенному сравнению видно, что без оптимизации судно тратило время на долгие переходы между профилями через всю площадь работ, тогда как возможна оптимальная траектория обхода.

ДОННЫЕ СТАНЦИИ

При работах в транзитной зоне и на акватории, с использованием донных станций, важным критерием является наличие самих донных станций на судне. Их количество определяется для каждого судна-раскладчика. Раскладчик не может выложить донных станций больше, чем у него есть на борту, для этого ему необходимо собрать станции из уже выложенных, т.е. повторно пройти по графу.

Профили для генератора и раскладчика в общем случае различны, более того, профили для источника и для раскладчика различаются в плане по интервалу между профилями и иногда по азимуту. На практике используется несколько раскладчиков, так как они могут раскладывать донное оборудование независимо.

Базовым для реализованного алгоритма является алгоритм построения маршрута для буксируемой установки, учет статических зон происходит по аналогии. Последовательность работы алгоритма для m судов-раскладчиков следующая:

1) задание начальной точки выхода судна;

2) определение параметров m + 1-судов: скорость, радиус разворота и т.д.;

3) определение максимального количества донных станций на раскладчиках;

4) загрузка погоды, создание запретных зон на ее основе;

5) создание временных зон и определение время действия данных участков;

6) построение оптимального маршрута и расписания работы раскладчиков:

а) решение задачи TSP для судна-источника по его профилям:

1) при создании последовательности профилей обхода учитывается как стоимость перехода с профиля на профиль, так и время сбора и раскладки профилей пунктов приема (донных станций), требуемых для регистрации при “отстреле” планируемого профиля;

2) построение маршрута аналогично построению для судна с методикой буксируемой установки;

б) определение очередности отработки шаблонов судами раскладчиками:

1) каждый из m раскладчиков определяет наиболее близкий ему профиль для раскладки и выкладывает на нем оборудование (число донных регистраторов на профиль известно);

2) на конечной вершине Vi на каждом профиле раскладчик принимает решение, основываясь на стоимости и количестве оставшихся на борту нодов, – произвести сбор уже освободившегося профиля или выкладывать далее. Освободившийся – профиль, который не участвует ни в одном из текущих шаблонов судна-источника и не будет участвовать в будущем, т.е. регистрация данных на котором закончена;

3) статические зоны при развороте, переходе между профилями обходятся по кривым Дубинса;

4) проверка расписания судов раскладчиков: если судно заходит на профиль, попадающий во временную зону, то производится перестроение маршрута с учетом того, что профиль закрыт в определенное временное окно.

Для тестирования алгоритма выбраны тестовые данные, предоставленные АО “МАГЭ”. Продолжительность маршрута составила 37 дней и 3 ч. Пример построения оптимального маршрута для задачи с буксируемым оборудованием представлена на рис. 7.

Рис. 7.

Окно графического интерфейса с решенной оптимальной задачей для синтетического примера с использованием методики донных станций; диаграмма Ганта отражает расписание судов источников и приемников.

ВЫВОДЫ

Предлагаемый алгоритм обеспечивает построение оптимального маршрута выполнения морских сейсмических работ с учетом быстроменяющихся параметров, таких как погода и ледовая обстановка, и не зависит от методики исследований. Траектория с использованием кривых Дубинса обеспечивает максимально близкую к реальности геометрию разворота и движения судов, обхода закрытых зон.

Тестирование работы алгоритма на реальных данных показало, что его применение позволяет обеспечить существенное сокращение времени, а следовательно – стоимости, проведения сейсморазведочных работ как при использовании буксируемого забортного оборудования, так и при проведении работ в транзитной зоне с использованием донных станций. Таким образом, выполненная разработка направлена, в частности, на интенсификацию освоения континентального шельфа Российской Арктики.

Впервые в мировой практике, благодаря применению методов искусственного интеллекта, создана система планирования морской сейсморазведки, позволяющая оптимизировать проведение работ для произвольного числа судов-укладчиков, с возможностью оптимизации используемого числа донных станций.

Полученные результаты применимы для дальнейшего использования при реализации задач по оптимизации плана работ сейсморазведочной морской съемки и автоматизации процессов обработки данных на судне.

Список литературы

  1. Caillau J.-B., Maslovskaya S., Mensch T., Moulinier T. Zermelo-Markov-Dubins Problem and Extensions in Marine Navigation. // CDC 2019 – 58th IEEE. Conference on Decision and Control. 2019. P. 1–7.

  2. Vermeer G. Acquisition/Processing -3D Seismic Survey Design Optimization // The Leading Edge. 2003. V. 22. № 10.

  3. Dokht R., Hamidreza R., Talebi M. Optimizing 3-D Seismic Survey Design Parameters Using Genetic Algorithm–a Case Study in Southwest of Iran // Arabian Journal of Geosciences. 2011. № 6. P. 1965–1975.

  4. Potvin J.-Y. Genetic Algorithms for the Traveling Salesman Problem // Annals of Operations Research. 1996. V. 63. P. 339–370.

  5. Gen M., Cheng R. Genetic Algorithms and Engineering Design, John Wiley & Sons Inc., London, UK. 1997. P. 407.

  6. Ahmed H.Z. Genetic Algorithm for the Traveling Salesman Problem Using Sequential Constructive Crossover Operator // Proceedings of the International Journal of Biometrics & Bioinformatics (IJBB). 2010. № 3. P. 96.

  7. Holland J.H. Adaptation in Natural and Artificial Systems // An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University of Michigan Press. Oxford, UK. 1975.

  8. Yuan S., Skinner B., Huang S., Liu D. A New Crossover Approach for Solving the Multiple Travelling Salesmen Problem Using Genetic Algorithms // European Journal of Operational Research. 2013. V. 228. № 1. P. 72–82.

  9. Sabba S., Chikhi S. Integrating the Best 2-Opt Method to Enhance the Genetic Algorithm Execution Time in Solving the Traveler Salesman Problem // Complex Systems and Dependability. Advances in Intelligent and Soft Computing. 2013. V. 170. P. 195–209.

  10. Dubins L.E. On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents // American Journal of Mathematics. 1957. V. 79. № 3. P. 497–516.

  11. Марков А.В., Симаньков В.И. Методика расчета траекторий полета беспилотных летательных аппаратов для наблюдения за местностью // Доклады БГУИР. 2019. № 4. 122. С. 57–62.

  12. Интернет ресурс, U.S. Geological Survey https://walrus.wr.usgs.gov/namss/survey/b-08-77-fl/

Дополнительные материалы отсутствуют.