АЛГОРИТМ ДЛЯ ЛИКВИДАТОРОВ

— Я бы это сформулировал так: мы занимаемся задачей снижения облучения персонала АЭС при выполнении работ в условиях повышенной радиации. А обратили внимание на эту проблему мы благодаря доценту кафедры атомных станций и возобновляемых источников энергии Уральского федерального университета Олегу Ташлыкову, который рассказал, как происходит процесс демонтажа радиационно опасных объектов.  

Допустим, стоит задача дезактивировать территорию, по которой в результате аварии разбросаны точечные источники излучения. Эти источники нужно посетить с соблюдением всех необходимых требований и как-то демонтировать, т.е. выключить. Доза облучения, получаемая исполнителями, существенно зависит от маршрута их перемещений в радиационных полях, от того, в какой последовательности они будут подходить к радиационно опасным объектам. В такой задаче есть немало ограничений. Прежде всего это так называемые условия предшествования (условие типа «одно после другого»), а также «стоимости» перемещений (т.е. дозы радиации), которые зависят от списка заданий, еще не выполненных на момент перемещения, поскольку исполнитель находится под воздействием тех и только тех источников, которые еще не демонтированы. 

— Чтобы создать алгоритм, а потом использовать его в различных приложениях, нужны прежде всего фундаментальные исследования, хорошая теория. Все задачи маршрутизации перемещений с выполнением работ в пунктах посещений исторически происходят от известной задачи коммивояжера, которая заключается в поиске самого выгодного маршрута, проходящего через указанные города по одному разу с последующим возвратом в исходный город. Задача коммивояжера считается трудно решаемой. А перед нами стоит еще более сложная задача, сопровождающаяся многими ограничениями. Как уже говорилось, они связаны с многовариантностью перемещений между пунктами и зависимостью от списка заданий, которые необходимо выполнить.

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

Первое, что нужно сделать в математике, — поставить задачу, причем, если учитывать все мелкие подробности, ничего не получится. Сначала необходимо найти точку старта, затем составить очередность посещений излучающих источников и траекторию процесса. Выбор очередности определяется многими факторами. Например, один источник излучения находится на другом: допустим, радиоактивный бак стоит на радиоактивной тумбе. Нижний источник можно демонтировать только после верхнего. Или другое ограничение: чтобы дезактивировать трубопровод, надо сначала «разобраться» с насосом.

Тут возникает парадокс: казалось бы, ограничения не способствуют оптимизации, а в нашем случае оказалось как раз наоборот. Наш алгоритм основан на нетрадиционном варианте динамического программирования, для которого не используется построение всего массива значений функции Беллмана. Если точно следовать его методу, надо произвести колоссальный объем вычислений. Но если посмотреть на задачу с другой стороны, то окажется, что далеко не все надо учитывать. И тогда можно строить не всю функцию Беллмана, а только те ее слои, или «куски», которые нам требуются для достижения наших целей. За счет того, что мы строим функцию не везде, а там, где надо, удается сэкономить ресурсы памяти.

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

Вообще в динамическом программировании много здравого смысла. Если сформулировать его суть совсем просто, то надо смотреть на шаг вперед и не ухудшать свое положение.

— Конечно. На тех же атомных станциях есть задачи, когда необходимо демонтировать энергоблоки, выведенные из эксплуатации. Такие проблемы существуют на Белоярской и Нововоронежской АЭС. Причем это задачи очень сложные: на энергоблоке часто нужно выполнять работы, никуда не двигаясь, или перемещаться приходится не по прямой линии, а вверх и вниз. Для того чтобы составить оптимальный маршрут и реализовать его на практике, нужен большой коллектив квалифицированных инженеров и программистов. Но сегодня это очень актуальная задача, и мы бы с удовольствием поучаствовали в ее решении.

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

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

Одна из таких задач — управление процессом листовой резки. Ее мы решаем в сотрудничестве с ведущим научным сотрудником лаборатории оптимального раскроя промышленных материалов и оптимальных маршрутных технологий УрФУ профессором Александром Петуниным. В задачах машиностроения, связанных с раскроем, нужно управлять движением режущего инструмента. Этот инструмент должен последовательно «посещать» окрестности контуров вырезаемых деталей при наличии большого числа разнообразных ограничений. Это в том числе те же условия предшествования, которые предписывают вырезать у деталей сначала внутренние контуры, и только после этого — внешний контур. Имеются и другие ограничения: жесткость листа и деталей, тепловые допуски. При этом работу нужно сделать за максимально короткое время.

Есть также задачи о морских и авиационных перевозках, где следует посетить большое число пунктов. Наш алгоритм может работать и в этих случаях: в частности, выбор оптимального маршрута позволяет уменьшить расход топлива.