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

На правах рукописи

Горбенко Анна Андреевна

МЕТОДЫ

КОМБИНАТОРНОЙ ВИРТУАЛИЗАЦИИ ДЛЯ МОБИЛЬНЫХ РОБОТОВ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

2 2 МАП'2014

Екатеринбург - 2014

005548717

005548717

Работа выполнена в ФГАОУ ВПО "Уральский федеральный университет имени первого Президента России Б.Н.Ельцина" на кафедре алгебры и дискретной математики Института математики и компьютерных наук.

Научный руководитель: Официальные оппоненты:

Попов Владимир Юрьевич, доктор физико-математических наук, доцент.

Корольков Юрий Дмитриевич, доктор физико-математических наук, профессор, ФГБОУ ВПО "Иркутский государственный университет", заведующий кафедрой прикладной алгебры и защиты информации Института математики, экономики и информатики;

Плющенко Андрей Николаевич, кандидат физико-математических наук, ЗАО "Восточный ветер - Eastwind", разработчик группы роуминга отдела биллинга.

ФГБУН "Институт математики и механики им. Н.Н.Красовского УрО РАН".

Защита состоится «20» июня 2014 г. в 12:00 часов на заседании диссертационного совета Д 212.285.25 на базе ФГАОУ ВПО "Уральский федеральный университет имени первого Президента России Б.Н.Ельцина" по адресу: 620000, г.Екатеринбург, пр. Ленина 51, зал заседаний диссертационных советов, коми. 248.

С диссертацией можно ознакомиться в библиотеке и на сайте ФГАОУ ВПО "Уральский федеральный университет имени первого Президента России Б.Н.Ельцина", http://dissovet.science.urfu.ru/news2/

Ведущая организация:

Автореферат разослан «М

01 Ц р 1 „ 2014 г.

Ученый секретарь диссертационного совета, доктор физико-математических наук, профессор

Пименов В.Г.

Общая характеристика работы

Актуальность темы. Исследование математических моделей, вычислительных методов и алгоритмов для робототехнических систем относится к одному из наиболее актуальных направлений современной математикиI1!Л2!. Особенно интенсивно в последние годы развивается проблематика, связанная с мобильными роботами.

Виртуализация — это общий подход, заключающийся в использовании некоторых методов абстрактного рассмотрения ресурсов. Наиболее интенсивно различные методы виртуализации применяются в программировании. Использование виртуализации делает программно-аппаратный комплекс существенно более универсальным. Методы виртуализации для роботов на сегодняшний день находятся на существенно более ранней стадии, чем для! компьютерных систем. Однако в робототехнике уже давно считается общепринятой необходимость использования абстрактных понятий и применения некоторых методов виртуализации при разработке комплексного программного обеспечения^3'.

Степень разработанности темы. В последние годы при построении различных математических моделей для робототехнических систем появился интерес к использованию закономерностей из области комбинаторики словМ,'5М6'. Хотя такой подход для робототехники является сравнительно новым, уже сейчас можно сказать, что его применение позволяет получать весьма точные и эффективные модели для различных конкретных задач. Важнейшим преимуществом использования закономерностей из области комбинаторики слов яв-

'Kelly A. Mobile robotics: mathematics, models, and methods / A. Kelly. -Cambridge: Cambridge University Press, 2013. -808 p.

2Kober J. Learning motor skills: from algorithms to robot experiments / J. Kober, J. Peters. -Cham: Springer, 2014. -201p.

3Hsieh M. Adaptive teams of autonomous aerial and ground robots for situational awareness: field reports / M. Hsieh, C. Cowley, J. Keller, L. Chaimowicz, B. Grocholsky, V. Kumar, C. Taylor, Y. Endo, R. Arkin, B. Jung, D. Wolf, G. Sukhatme, D. MacKenzie // Journal of field robotics. -2007. -Y.24, N.11-12. -P.991 -1014.

4 Argyros A. Robot homing by exploiting panoramic vision / A. Argyros, K. Bekris, S. Orphanoudakis, L. Kavraki // Autonomous robots. -2005. -V.19, N.l. -P.7 -25.

sLamon P. Deriving and matching image fingerprint sequences for mobile robot localization / P. Lamon, I. Nourbakhsh, B. Jensen, R. Siegwart // Proceedings of the IEEE international conference on robotics and automation. —Piscataway: IEEE Press, 2001. -P. 1609 -1614.

6Pradel G. Symbolic trajectory description in mobile robotics / G. Pradel, C. Caleanu // Mobile robots: perception & navigation. -Rijeka: InTech, 2007. -P.543 -570.

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

Несмотря на очевидные преимущества, которые может дать комбинаторная виртуализация в робототехнике, на сегодняшний день существенным препятствием для активного использования этого метода в робототехнике является то, что большинство задач поиска комбинаторных закономерностей относится к классу вычислительно трудных проблем. Наличие вычислительно эффективных алгоритмов для решения трудных проблем комбинаторики слов позволило бы существенно повысить качество многих математических моделей комбинаторной виртуализации для роботов. Задача 3-вынолнимости (3SAT) является одной из наиболее известных и хорошо изученных NP-полных проблем'7!. для проблемы 3SAT разработано большое количество эффективных алгоритмов!7!, обычно называемых SAT-решателями. Нахождение сведения к 3SAT широко применяется для решения различных вычислительно трудных проблем. Естественно использовать такой подход и в робототехнике. Математически строгая формализация этого подхода может быть дана с использованием конструктивного полиномиального сведения схс в рамках вычислительной логики предикатов С PL (computational predicate logic), удовлетворяющей системе аксиом Рейтинга!8!. Конструктивное полиномиальное сведение проблемы А к проблеме В мы в дальнейшем будем обозначать С PL Ь А осс В.

Для практического использования некоторой комбинаторной проблемы А в робототехнике получения С PL h А <хс 3SAT недостаточно. Необходимо для данного сведения CPL А ссс 3SAT найти SAT-решатель, который будет демонстрировать высокую эффективность на робототехнических данных с использованием вычислительных возможностей, которые доступны робототехническому комплексу. Более того, робототехпическим комплексам, кроме решения той или иной комбинаторной проблемы, одновременно необходимо решать и ряд других задач. Поэтому решатель должен быть тем или иным образом интегрирован в общую вычислительную систему робота. Естественно возникает вопрос о разработке некоторого обще-

7Kilani Y. А survey of the satisfiability-problems solving algorithms / Y. Kilani, M. Bsoul, A. Alsarhan, A. Al-Khasawneh // International journal of advanced intelligence paradigms. -2013. -V.5, N.3. -P.233 -25G.

8Constable R. Formalizing decidability theorems about automata / R. Constable // Computational logic. NATO ASI Series. Scries F: computer and systems sciences. -1999. -V.165. —P. 179 -213.

,суперкомпьте-ение мобильно-1ичным для рока математиче-

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

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

В зависимости от типа робота, его сенсоров, решаемых задач, условий функционирования, а также ряда других факторов в архитектуре робота могут быть выделены различные системы. Часть систем может быть отнесена к специфике задач, решаемых роботами. Однако присутствие некоторых систем очевидным образом определяется архитектурой рассматриваемого класса роботов. Для мобильного робота с одним визуальным сенсором к таким системам относятся: система обработки моторных примитивов; визуальная система навигации; система распознавания изображений. Исследование метода комбинаторной виртуализации для мобильного робота с одним визуальным сенсором естественным образом разбивается на разра-

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

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

Теоретическая и практическая значимость работы. Работа носит теоретический характер. Ее результаты могут быть иснользова-ны для дальнейших исследований в области математического моделирования для интеллектуальных мобильных роботов. Кроме того, результаты работы обеспечивают теоретический фундамент для создания эффективных систем управления мобильных сервисных роботов, что делает естественным их применение в робототехнике. Основные методы исследований. Основными методами исследований являются методы математического моделирования; математической логики и теории алгоритмов; интеллектуальных систем; численных методов; вычислительного эксперимента; автоматического программирования. В частности, в диссертации используются методы как классической логики, так и вычислительной логики предикатов. Активно применяются различные тины нейронных сетей. Среди нейросетевых методов одним из основных является вычислительный метод, основанный на нейронных сетях Рунге — Кутты. Мы рассматриваем церсептронные и рекуррентные нейронные сети Рунге — Кутты 4 порядка. Их обучение основано на градиентных и нелинейных рекурсивных алгоритмах. Используются как классические, так и коэволюционные генетические алгоритмы. Применяются различные варианты фильтра Калмана.

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

• метод комбинаторной виртуализации системы обработки примитивов двигателя на основе проблемы поиска приближенного периода;

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

• метод комбинаторной виртуализации для оптимизации множества алгоритмов распознавания системы распознавания изображений на основе проблемы покрытия стеков.

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

Результаты диссертации были представлены на следующих конференциях: 9-я Международная конференция "Высокопроизводительные параллельные вычисления на кластерных системах" (Владимир, 2009г.); Межвузовская научная конференция по проблемам информатики "СПИСОК - 2009" (Екатеринбург, 2009г.); Итоговая конференция XIV областного конкурса научно-исследовательских работ студентов учреждений высшего и среднего профессионального образования Свердловской области (НИРС) "Научный Олимп" (Екатеринбург, 2011г.); 42-ая Всероссийская молодежная конференция "Современные проблемы математики" (Екатеринбург, 2011г.); The 4th international conference on advanced computer control (Shanghai, China, 2012); Научно-технический семинар "Робототехника и безлюдные технологии. Перспективы развития и возможности Ур-ФУ" (Екатеринбург, 2013г.); The 2nd international conference on machine design and manufacturing engineering (Jeju Island, South Korea, 2013); The 3rd international conference on computcr-aided design, manufacturing, modeling and simulation (Chongqing, China, 2013); The 11th international conference of numerical analysis and

applied mathematics (Rhodes, Greece, 2013); The 3rd international conference 011 advanced materials and engineering materials (Singapore, 2013). Также результаты диссертации регулярно докладывались на научном семинаре отдела интеллектуальных систем и робототехники РУНЦ "Интеллектуальные системы и информационная безопасность" Института математики и компьютерных паук УрФУ. Результаты также были представлены на Уральской международной выставке и форуме промышленности и инноваций ИННОПРОМ-2010 и третьей международной выставке и форуме промышленности и инноваций ИННОПРОМ-2012 (Екатеринбург, 2010г. и 2012г.).

По теме диссертации опубликовано 13 научных работ, из них 9 в изданиях, входящих в систему цитирования Scopus; получены свидетельство о регистрации программы для ЭВМ и патент на полезную модель.

Личный вклад. Все результаты диссертационной работы получены автором лично.

Свидетельство о регистрации программы для ЭВМ и патент на полезную модель получены в соавторстве. Свидетельство о регистрации программы для ЭВМ получено для управляющей программы гусеничного робота Kuzmn^II, состоящей из двух частей: низкоуровневой и высокоуровневой. Низкоуровневая часть была разработана и реализована A.C. Шекой. Э та часть отвечает за непосредственный доступ к сенсорам и двигателям робота. Высокоуровневая часть была разработана и реализована автором. Эта часть отвечает за системы навигации и распознавания. Патент на полезную модель включает большое количество различных подсистем, из которых автору принадлежит серверная система распознавания. Из результатов, отраженных в свидетельстве о регистрации программы для ЭВМ и патенте па полезную модель, в диссертацию включены только принадлежащие лично автору.

Структура и объем работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы, содержащего 192 наименования, и списка иллюстративного материала. Общий объем диссертации составляет 143 страницы. Она содержит 31 рисунок и 25 таблиц.

Основное содержание работы

В первой главе рассмотрен метод комбинаторной виртуализации для системы обработки моторных примитивов. Метод основан па хорошо известном подходе к классификации моторных примитивов, созданию их систем и использовании при обучении, предполагающем выделение однотактных и ритмических демонстраций'9!, а также на символьном подходе к описанию траекторий!6' при помощи вычисления алфавитно-взвешенного редакционного расстояния'10!, которое обычно называют расстоянием Левенштейна, и применения закономерностей комбинаторики слов. Предложенный в диссертации метод использует систему подтверждения выполнения команд роботом на основе конструктивной логики'8!"!11!; автоматическое порождение роботом алфавитов примитивов двигателя и расстояния Левенштейна; модель сравнения последовательностей примитивов при помощи поиска приближенного периода'12!.

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

Теорема 1. CPL Ь АР ас 3SAT.

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

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

sKober J. Learning motor primitives for robotics / J. Kober, J. Peters // Proceedings of the IEEE international conference on robotics and automation. — Piscataway: IEEE Press, 2009. -P.2112 -2118.

10Гасфилд Д. Строки, деревья и последовательности в алгоритмах / Д. Гас-филд. -СПб.: Невский Диалект, 2003. -654 с.

11 O'Connor R. Classical mathematics for a constructive world / R. O'Connor // Mathematical structures in computer science. -2011. -V.21. -P.861 -882.

12Sim J. Approximate periods of strings / J. Sim, C. Iliopoulos, K. Park, W. Smyth // Theoretical computer science. -2001. -V.262, N.l-2. -P.557 -568.

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

Вторая глава посвящена вопросам комбинаторной виртуализации визуальных систем навигации. В рамках наиболее распространенных взглядов на построение визуальных систем навигации для современных автономных сервисных роботов наибольший интерес представляет топологическая навигация!4!'!5!'!6!'!13!. При этом с точки зрения комбинаторной виртуализации можно выделить следующие три проблемы: построение панорамного изображения; выбор конкретного множества дорожных знаков; совмещение дорожных знаков на различных изображениях!4!'!5!'!14!'!15].

Для построения панорамного изображения рассматривался ряд подходов, основанных на использовании закономерностей комбинаторики слов: кратчайшей общей надстроки, кратчайшей общей над-иоследовательности и кратчайшей общей упорядоченной надпосле-дов ательности (SCOS)!16!. Вычислительные эксперименты показали, что количество правильно построенных панорам, полученных при помощи решения проблемы SCOS, превосходит аналогичный результат для других моделей в 2 — 4 раза и для различных роботов составляет от 78 % до 97 % от общего количества панорам'16!. Поэтому для комбинаторной виртуализации построения панорамного изображения в диссертации рассмотрена проблема SCOS.

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

Теорема 2. С PL h SCOS ссс 3SAT.

При наличии доступа к внешним вычислительным ресурсам робот обращается к ним для нахождения решения проблемы SCOS при

13Goedeme Т. Robust vision-only mobile robot navigation with topological maps / T. Goedeme, L. Van Gool // Motion planning. -Rijeka: InTech, 2008. -Chapter 4. -P.63 -88.

14Brown M. Automatic panoramic image stitching using invariant features / M. Brown, D. Lowe /'/ International journal of computer vision. -2007. —V.74, N.l. -P.59 -73.

15Michel D. Horizon matching for localizing unordered panoramic images / D. Michel, A. Argyros, M. Lourakis // Computer vision and image understanding. -2010. -V.114, N.2. -P.274 -285.

16Popov V. Building the panoramic image for mobile robot localization / V. Popov, A. Gorbenko // Applied mechanics and materials. -2013. -V.365-366. -P.967 -970.

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

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

Следует отметить, что в робототехнике для моделирования конкретных множеств дорожных знаков широко используются циклические строки^'М. Эффективность этой модели 'считается общепризнанной. Поэтому для комбинаторной виртуализации выбора конкретного множества дорожных знаков естественно использовать некоторый метод сравнения циклических строк. Для выбора конкретного множества дорожных знаков было предложено использование проблем существования циклического центра (CCS) и циклического центра с фиксированными буквами (CCSFL)'17'. Результаты экспериментального сравнительного исследования продемонстрировали высокую эффективность применения CCS и CCSFL'17'. В частности, результаты экспериментального исследования показали, что хотя использование CCSFL в общем случае обеспечивает более высокую точность навигации, чем CCS, fia практически значимых для современных роботов дистанциях CCSFL и CCS отличаются лишь незначительно'17!, в частности, на дистанции 10 метров отклонение от цели для CCS больше отклонения от цели для CCSFL всего на 2 сантиметра'17'. Поэтому использования только CCS для выбора конкретного множества дорожных знаков на сегодняшний день вполне достаточно. А рассмотрение CCSFL представляет (ш-терес преимущественно в перспективе дальнейшего развития робототехники.

Заметим, что NP-полнота проблемы CCS является несложным следствием NP-полноты проблемы существования центра'18'. Поэто-

17Popov V. The problem of selection of fingerprints for topological localization / V. Popov // Applied mechanics and materials. -2013. -V.365-366. -P.946 -949.

18Frances M. On covering problems of codes / M. Frances, A. Litman // Theory of computing systems. -1997. -V.30, N.2. -P.113 -119.

му представляет интерес следующее утверждение.

Теорема 3. CPL Н CCS ссс 3SAT.

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

Подход к совмещению дорожных знаков, основанный на использовании поиска наибольшей общей подпоследовательности, хорошо известен М. В диссертации для комбинаторной виртуализации совмещения дорожных знаков применяется обобщение этой комбинаторной проблемы — проблема существования наибольшей общей подпоследовательности с ограничениями (C-LCS)'19!. Поскольку проблема C-LCS является NP-ircb-uroiil19', представляет интерес следующее утверждение.

Теорема 4. CPL Ь C-LCS ссс 3SAT.

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

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

19GotthUf Z. Constrained LCS: hardness and approximation / Z. Gotthilf, D. Hermeliii, M. Lewenstein // Lecture notes in computer science. -2008. -V.5029. -P.255 -262.

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

Следует отметить, что хотя первые работы по автоматическому порождению модулей распознавания изображений появились еще в 80-е годы XX века, многие ключевые вопросы в этой области до сих пор остаются без ответа!21'. Важнейшим препятствием па пути распространения использования известных па сегодняшний день методов автоматического порождения модулей распознавания является наличие тесной связи между вычислительной сложностью того или иного детерминированного метода и его выразительными возможностями'21!. Исходя из этого, для современного робота вопрос автоматического порождения модулей распознавания естественно рассматривать только в контексте порождения интеллектуальных анализаторов. Использование большого количества анализаторов существенно понижает производительность системы распознавания. Поэтому необходим механизм, который определял бы количество и порядок использования анализаторов.

В третьей главе рассмотрен общий подход к автоматическому порождению интеллектуальных модулей визуального распознавания и метод комбинаторной виртуализации оптимизации множества алгоритмов распознавания, основанный на поиске решений для проблемы покрытия стеков (SC)'22'. Следует отметить, что использование задачи SC позволяет найти оптимальное решение для последовательности классификации по признакам в рамках хорошо известной и активно развивающейся системы неокогнитрона!23!''24'. Поскольку проблема SC является NP-полной!22', представляет интерес следу-

20Журавлев Ю.И. Распознавание образов и распознавание изображений /' Ж.И. Журавлев, И.Б. Гуревич // Ежегодник "Распознавание. Классификация. Прогноз. Математические методы и их применение". —М.: Наука, 1989. —2 вып. — С.5 -72.

21 Andreopoulos А. 50 Years of object recognition: directions forward / A. Andreopoulos, J. Tsotsos // Computer vision and image understanding. -2013. -V.117, N.8. —P.827 -891.

22Gerbush M. Approximating minimum reset sequences / M. Gerbush, B. Heeringa // Lecture notes in computer science. —2011. -V.6482. -P.154 —162.

23Fukushima K. Neocognitron: a self-organizing neural network model for a mechanism of pattern recognition unaffected shift in position / K. Fukushima ,// Biological cybernetics. -1980. -V.36, N.4. -P.193 -202.

24Pukushima K. Artificial vision by multi-layered neural networks: neocognitron and its advances / K. Fukushima // Neural networks. -2013. -V.37. -P. 103 -119.

ющее утверждение.

Теорема 5. CPL h SC ссс 3SAT.

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

В четвертой главе рассмотрены вопросы, относящиеся непосредственно к разработке исследовательского программного комплекса, созданного для исследования проблем, обозначенных в первых трех главах, получения данных для тестирования алгоритмов, проведения вычислительных и робототехнических экспериментов. В частности, в четвертой главе представлена общая модель программного комплекса. Рассмотрены основные инструменты автономного функционирования при невозможности подключения к внешним вычислительным ресурсам. Также в четвертой главе предложен алгоритм обучение на одном примере с помощью имитации, который представляет интерес для начальной настройки робота и получения экспериментальных данных. Этот алгоритм основан на использовании подхода'25!, заключающегося в минимизации отклонения траектории робота Р' от продемонстрированной траектории Р при помощи функции энергии'26!

к

Е = £ Il P'w - Рш II +Л(/) J J 2 (/£ + Vly + fZ„)dzdy,

W=1

где II Р^ — Рш Л — расстояние между соответствующими контрольными точками траекторий Р и Р', / : Р —► Р'. В диссертации в качестве А(/) рассматривается функция, вычисляемая при помощи нейронной сети Рунге — Кутты'27!.

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

2sWu Y. Towards one shot learning by imitation for humanoid robots / Y. Wu, Y. Demiris // Proceedings of the IEEE international conference on robotics and automation. -Piscataway: IEEE Press, 2010. -P.2889 -2894.

26Bookstein F. Principal warps: thin-plate splines and the decomposition of deformations /' F. Bookstein // IEEE transactions on pattern analysis and machine intelligence. -1989. -V.ll, N.6. -P.567 -585.

27Wang Y.-J. Runge-Kutta neural network for identification of dynamical systems in high accuracy / Y.-J. Wang, C.-T. Lin // IEEE transactions on neural networks. -1998. -V.9, N.2. -P.294 -307.

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

Следует отметить, что в случае необходимости получения оптимальных решений при невозможности подключения к внешним вычислительным ресурсам в программном комплексе реализован • разработанный диссертантом бортовой SAT-решатель: алгоритм GSAT'28' с адаптивной функцией оценки. Для вычисления значений адаптивной функции оценки в диссертации используются нейронные сети Рунге - Кутты. Описание этого алгоритма и вычислительных экспериментов приведены в четвертой главе. При использовании хорошо обученного генетического алгоритма ^ля адаптации SAT-решатель, предложенный в диссертации, в сравнении с ранее разработанным аналогом'29', незначительно уступая (1 %) в количестве правильных решений, существенно выигрывает в важнейшей для бортового алгоритма характеристике — скорости {7 раз).

В четвертой главе приведены результаты общего [тестирования программного обеспечения робота. Это тестирование показало, что метод комбинаторной виртуализации можно использовать для современных мобильных роботов. При этом в комнатном окружении скорость работы робота Neato XV-11 с бортовым компьютером Sony Vaio PCG-Sllllv, на котором проводилось тестирование, в автономном режиме уступала скорости телеуправляемого режима не более чем в 1.5 раза (см. таблицу 1).

Таблица 1 - Среднее значение отношения скорости решения задачи под управлением автономной системы к скорости решения той же задачи в телеуправляемом режиме, где Ь — обозначает длину траектории (в метрах), а Л — количество поворотов.

0 < L < 10 9 < L < 20 19 < L < 40 39 < L < 60

0 < R < 5 1.082 1.097 1.119 1.303

4 < R < 10 1.094 1.111 1.134 1.342

9 < R < 20 1.109 1.129 1.187 1.433

28Selman B. A new method for solving hard satisfiability problems / B. Selman, H. Levesque, D. Mitchell // Proceedings of the 10th national conference on artificial intelligence. -Palo Alto: AAAI Press, 1992. -P.440 -446.

29Popov V. GSAT with adaptive score function / V. Popov // Advanced studies in theoretical physics. -2013. -V.7, N.8. -P.363 -366.

Основные результаты диссертации

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

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

• система вычислительных методов, обеспечивающих эффективное. применение моделей комбинаторной виртуализации:

— система вычислительных методов для нахождения оптимальных решений с использованием внешних вычислительных ресурсов, основанная на конструктивных сведениях к проблеме ЗБАТ и применении БАТ-решателей;

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

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

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

Работы автора по теме диссертации

Статьи, опубликованные в рецензируемых научных изданиях, определенных ВАК:

1. Gorbenko A. A graph-based model of object recognition self-learning -

/ A. Gorbenko // Advanced studies in theoretical physics. -2013. -V.7, N.3. -P.115 -120.

2. Gorbenko A. A system of intelligent algorithms for a module

of onboard equipment of mobile vehicles / A. Gorbenko // International journal of mathematical analysis. -2013. -V.7, N.47. -P.2317 -2331.

3. Gorbenko A. Automatic generation of modules of object categorizati-

on for autonomous mobile robots / A. Gorbenko // AIP conference proceedings. -2013. -V.1558. -P.2087 -2090.

4. Gorbenko A. Automatic generation of modules of visual recognition /

A. Gorbenko // Applied mechanics and materials. -2013. -V.416-417. -P.748 -752.

5. Gorbenko A. Graph-theoretic models for the module of safe planning

for control systems of mobile robots / A. Gorbenko // Advanced materials research. -2013. -V.683. -P.737 -740

G. Gorbenko A. On the constrained longest common subsequence problem / A. Gorbenko // IAENG international journal of computer science. -2013. -V.40, N.4. -P.266 -273.

7. Gorbenko A. The problem of fingerprints selection for topological

localization / A. Gorbenko // Engineering letters. -2013. -V.21, N.4. -P.212 -217.

8. Gorbenko A. The shortest common ordered supersequence problem

/ A. Gorbenko // Applied mathematical sciences. -2013. -V.7, N.97. -P.4813 -4819.

9. Gorbenko A. On the approximate period problem / A. Gorbenko

// IAENG international journal of applied mathematics. -2014. -V.44, N.l. -P.l -9.

Другие публикации:

10. Горбенко А.А. Программный комплекс обработки робототех-нической видеоинформации для построения трехмерных координат объектов / А.А. Горбенко // Труды межвузовской научной конференции по проблемам информатики "СПИСОК-2009". -Екатеринбург: Издательство Уральского государственного университета, 2009. -С.53 -55.

11. Горбенко А.А. Автоматическое порождение специализированных нейронных сетей / А.А. Горбенко // Труды 42-ой всероссийской молодежной школы-конференции "Современные проблемы математики". -Екатеринбург: Издательство института математики и механики УрО РАН, 2011. -С.308 -310.

12. Горбенко А.А. Система управления гусеничного робота Kuzma-

II / А.А. Горбенко// Тезисы студенческих научных работ XIV Областного конкурса научно-исследовательских работ студентов "Научный Олимп". Направление "Естественные науки". -Екатеринбург: Издательство Уральского федерального университета, 2011. -С.7 -8.

13. Gorbenko A. An intelligent self-learning algorithm for safe cooperation in industrial environments / A. Gorbenko // CD proceedings of the 3rd international conference on advanced materials and engineering materials. -Singapore, 2013.

Патенты и свидетельства о регистрации программ:

14. Вихарев С.В., Шека А.С., Брусянин Д.А., Попов В.Ю., Горбенко

А.А. Пат. 121628 Российская Федерация, МПК G07C. Интеллектуальная система анализа пассажиропотоков с использованием технического зрения; заявитель и патентообладатель Общество с ограниченной ответственностью "БрейнКрафт" (RU).

- №2012110674; заявл. 20.03.2012; опубл. 27.10.2012, Бюл. №30.

- 2 е.: ил.

15. Шека А.С., Горбенко А.А. Свидетельство о государственной ре-

гистрации программы для ЭВМ №2012616119 "Управляющая программа гусеничного робота Kuzma-IF. Федеральная служба по интеллектуальной собственности. Зарегистрировано 4 июля 2012 г.

Подписано в печать 16.04.2014. Формат 60 х 84 1/16 Усл. печ. л. 1,16. Тираж 100 экз. Заказ №247

Копировальный центр «Копи-А» 620027, Екатеринбург, ул. Мамина-Сибиряка, 71

Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Уральский федеральный университет имени первого Президента России Б.Н.Ельцина"

На правах рукописи

04201459105

Горбенко Анна Андреевна

МЕТОДЫ

КОМБИНАТОРНОЙ ВИРТУАЛИЗАЦИИ ДЛЯ МОБИЛЬНЫХ РОБОТОВ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель

доктор физико-математических наук,

доцент В.Ю. Попов

Екатеринбург - 2014

Оглавление

Введение ..................................................................... 4

Глава 1. Система обработки моторных примитивов ........................19

1.1 Математическая модель системы обработки примитивов .........22

1.2 Вычислительные методы для комбинаторной виртуализации системы обработки моторных примитивов .........................28

1.3 Экспериментальные исследования для метода комбинаторной виртуализации системы обработки моторных примитивов ........50

Глава 2. Визуальная система навигации ....................................55

2.1 Проблема построения панорамного изображения..................57

2.1.1 Вычислительные методы для комбинаторной виртуализации построения панорамного изображения......60

2.1.2 Экспериментальные исследования для метода комбинаторной виртуализации построения

панорамного изображения ..................................64

2.2 Проблема выбора конкретного множества дорожных знаков......65

2.2.1 Вычислительные методы для комбинаторной виртуализации выбора множества дорожных знаков .......68

2.2.2 Экспериментальные исследования для метода комбинаторной виртуализации выбора

множества дорожных знаков................................71

2.3 Проблема совмещения дорожных знаков на

различных изображениях ..........................................74

2.3.1 Вычислительные методы для комбинаторной виртуализации совмещения дорожных знаков

на различных изображениях ................................78

2.3.2 Экспериментальные исследования для метода комбинаторной виртуализации совмещения

дорожных знаков на различных изображениях .............80

Глава 3. Система распознавания изображений ..............................84

3.1 Оптимизация множества алгоритмов распознавания ..............88

3.1.1 Вычислительные методы для комбинаторной виртуализации оптимизации множества

алгоритмов распознавания ..................................89

и

3.1.2 Экспериментальные исследования для метода комбинаторной виртуализации оптимизации множества алгоритмов распознавания ......................91

Глава 4. Программный комплекс............................................93

4.1 Система алгоритмов ...............................................95

4.1.1 Обучение на одном примере с помощью имитации .........96

4.1.2 Бортовой ЭАТ-решатель ....................................98

4.1.3 Система безопасного планирования........................100

4.1.4 Алгоритм самообучения распознаванию объектов.........103

4.2 Исследовательские роботы .......................................107

4.3 Общее описание программного обеспечения ......................113

4.4 Общее тестирование программного обеспечения робота..........123

Заключение ................................................................125

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

Список иллюстративного материала.......................................141

Введение

Актуальность темы. Исследование различных вопросов разработки математических моделей, вычислительных методов и алгоритмов для робототехниче-ских систем относится к одному из наиболее актуальных направлений современной математики [5,6,10,12,13,15,117]. Особенно интенсивно в последние годы развивается проблематика, связанная с мобильными роботами [39,45,95,102].

Виртуализация — это общий подход, заключающийся в использовании некоторых методов абстрактного рассмотрения ресурсов. Наиболее интенсивно различные методы виртуализации применяются в программировании (см., например, [24,29,94,159]). Использование виртуализации позволяет выносить связи с конкретными ресурсами за рамки программного, программно-аппаратного или аппаратного комплекса, что делает соответствующий комплекс существенно более универсальным.

Следует отметить, что развитие технологий создания программного обеспечения и соответствующих математических моделей для робототехнических систем во многом повторяет аналогичные процессы для компьютерных систем. Однако эти процессы для роботов на сегодняшний день находятся на существенно более ранней стадии, чем для компьютерных систем (см., например, [22,86,96,139]). Сегодня для роботов нет аналогов ОС Microsoft Windows или ОС Linux. Во многом это обусловлено тем, что в робототехнике математические модели виртуализации разработаны пока очень слабо. Кроме того, робототехника выдвигает значительно большие требования к виртуализации, чем компьютерные системы. В частности, в робототехнике виртуализация необходима не только на уровне чисто вычислительных процессов, но и для мехатрони-ки, сенсорики. Процессы взаимодействия между устройствами, с окружением и пользователями для роботов существенно более сложны и многогранны, чем для компьютерных систем. Несмотря на существенное отставание от компьютерных систем, в робототехнике уже довольно давно считается общепринятой необходимость использования абстрактных понятий и применения некоторых методов виртуализации при разработке комплексного программного обеспечения [84].

Степень разработанности темы. В последние годы при построении различных математических моделей для робототехнических систем появился интерес к использованию закономерностей из области комбинаторики слов. Поиск наибольшей общей подпоследовательности применяется в техническом зрении для склеивания результатов трехмерного лазерного сканирования [121]; в алгоритмах визуальной навигации мобильных роботов для уменьшения неопределенности при мониторинге особенностей [19]; в алгоритмах лазерной навигации мобильных роботов для локализации на карте [16]; при эволюционировании архитектуры системы управления робота [75]; при обучении робота-графопостроителя в качестве меры подобия траекторий [127]; в обучении роботов на уровне задач для обобщения опыта [119]. Модифицированный вариант наибольшей общей подпоследовательности используется в техническом зрении для представления действий траекториями [23,125,164]. Поиск разделяющих подпоследовательностей используется мобильными роботами при распознавании звуковых сигналов [123]. Следует отмстить, что различные иерархические

модели обучения уже давно исследуются в теории искусственного интеллекта. Среди таких моделей можно отметить избирательные модели, параллельные, последовательные, неупорядоченные [124]. Однако в робототехнике иерархические методы стали применять сравнительно недавно. В частности, можно отметить робототехнические симуляторы [37,38], реализации для реальных роботов [35, 36, 91] и программное обеспечение [145] для гуманоидных роботов NAO1 и iCub2. В работе [168] предложен метод иерархического обучения движению гуманоидного робота, основанный на поиске для строки, представляющей собой последовательность действий, минимального покрытия без пересечений подсловами из известного множества. В работе [56] рассмотрен сравнительный анализ трех различных алгоритмов сравнения строк с точки зрения их эффективности при решении задачи локализации робота, использующего визуальную систему навигации по дорожным знакам. В работах [137,138] для строк, представляющих описание траекторий мобильных роботов, рассмотрены мера близости, предложенная в [82], расстояния Хэмминга и Левенштейна, а также кросс-корреляционная мера близости.

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

Несмотря на очевидные преимущества, которые может дать комбинаторная виртуализация в робототехнике, на сегодняшний день существенным препятствием для активного использования этого метода в робототехнике является то, что большинство задач поиска комбинаторных закономерностей относится к классу вычислительно трудных проблем. В частности, в работе [121] применяются наибольшие общие подпоследовательности множества строк. Проблема нахождения наибольшей общей подпоследовательности множества строк является NP-трудной. В работе [121] для ее решения предлагается применять полный перебор (brute force) [154]. В работе [125] при сравнении двух множеств строк рассматриваются наибольшие общие подпоследовательности только пар строк. При эволюционировании архитектуры системы управления робота [75] для измерения генетической конвергенции популяции применяется поиск наибольшей общей подпоследовательности двух случайным образом выбранных генотипов, хотя очевидно, что рассмотрение некоторых множеств генотипов было бы более информативно. Используемая при локализации на карте [16] наибольшая общая подпоследовательность двух строк, представляющих результаты сканирования, дает недостаточно точные результаты, что заставляет применять

1Aldebaran Robotics. URL: http://www.aldebaran-robotics.com/en/

2iCub. URL: http://www.icub.org/

систему из двух дополнительных фильтров. При обучении роботов на уровне задач для обобщения опыта необходимость использования более сложной комбинаторной модели, чем наибольшая общая подпоследовательность двух строк, применявшаяся в [119], отмечена, например, в [42]. В работе [168] не рассматривается возможность изменения последовательности действий. Это, вообще говоря, приводит к факториальному замедлению процесса обучения. Однако рассмотрение возможности изменения последовательности действий потребует решения NP-трудной задачи поиска минимального разбиения множества на подмножества.

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

Один из наиболее распространенных подходов к поиску эффективных алгоритмов для вычислительно трудных задач основан на использовании сведений к проблеме выполнимости.

Проблема выполнимости (SAT):

Дано: Булева функция f(xь ..., хп).

вопрос: Существуют ли значения Xi,..., хп такие, что f(xь ..., хп) = 1?

Проблема SAT является ключевой задачей в математической логике и теории вычислений. Доказательство NP-полноты этой проблемы было дано С. Куком в 1971 году [33]. До этого времени понятия NP-полных проблем еще не существовало. На практике проблема выполнимости является основополагающей в решении многих задач в теории автоматического доказательства, системах автоматизированного проектирования, автоматизированном производстве, машинном зрении, теории баз данных, робототехнике, разработке интегральных схем, разработке архитектур компьютеров, разработке компьютерных сетей. Проблема SAT является наиболее изученной NP-полной проблемой [69,97]. Часто SAT рассматривается для булевых функций в конъюнктивной нормальной форме (КНФ). Особенно интенсивно изучается важный частный случай SAT, относящийся к булевым функциям в конъюнктивной нормальной форме, в которой каждая дизъюнкция содержит ровно 3 переменных или их отрицания (3-КНФ).

Проблема 3-выполнимости (3SAT):

дано: Булева функция f(xi,... ,жп) в 3-КНФ.

Вопрос: Существуют ли значения ..., хп такие, что f(xь ..., хп) = 1?

Отметим, что как и SAT, проблема 3SAT является NP-полпой [126].

Для SAT разработано много высокоэффективных алгоритмов [69], которые обычно называют SAT-решателями. В частности, разработано много методов оптимизации, параллельных и эвристических алгоритмов (см., например, [69]). Предложено несколько генетических алгоритмов [46,74,92,165]. Также рассмотрены гибридные алгоритмы, в которых подход генетических алгоритмов комбинирован с алгоритмами локального поиска [73]. Современные решатели для

SAT в основном разработаны для булевых функций в КНФ. В частности, для решения задачи выполнимости в КНФ успешно применялись методы стохастического локального поиска. В последнее время решатели, работающие с произвольными булевыми функциями, показали, что существуют преимущества при решении пропозициональной проблемы выполнимости в более выразительном естественном представлении, поскольку преобразование формулы в КНФ может привести к потере структуры проблемы и появлению значительно большего количества переменных для кодирования задачи. Решатели, использущие КНФ, могут проигрывать на проблемах, для которых более естественно кодирование произвольной пропозициональной формулой. Представление формулы в виде КНФ может экспоненциально увеличить размер формулы или значительно уменьшить эффективность использования булевых функций вообще. Перевод может привести к появлению множества новых переменных, которые увеличивают размер пространства поиска решателя. Отметим, что имеется и существенный интерес к разработке алгоритмов, которые способны работать не только с конъюнктами (см., например, [116,149]). Сравнительно высокую эффективность показывают алгоритмы, основанные только на локальном поиске. Конечно, данные алгоритмы в худшем случае требуют экспоненциального времени. Но на основании экспериментальных данных они могут относительно быстро получить решения для большинства булевых функций. Отметим, что у возможности быстро решать NP-полные проблемы есть и теоретическое обоснование, связанное с невозможностью для 3SAT доказательства NP-полноты в среднем относительно естественного сведения [32,70].

Наличие большого количества эффективных SAT-решателей делает естественным использование сведения к различным версиям проблемы выполнимости для решения вычислительно трудных задач. В последнее время большой интерес вызвало кодирование задач проблемой выполнимости и их решение высокоэффективными алгоритмами, разработанными для задачи выполнимости. В частности, алгоритмы локального поиска дали впечатляющие результаты для многих задач. Например, существует несколько вариантов SAT-кодирования проблемы CSP3, клики, задачи планирования и раскраски графов. Задачи нахождения максимального разреза, вершинного покрытия и максимального независимого множества могут быть сведены к MAX-2-SAT4. Существует ряд явных сведений задачи нахождения гамильтонова пути к проблеме 3SAT.

Если существует полиномиальный алгоритм F, который трансформирует произвольные начальные данные х проблемы А б NP в начальные данные F(x) проблемы В € NP так, что для F(x) существует вычисление, возвращающее 1, тогда и только тогда, когда для х существует вычисление, возвращающее 1, то говорят, что проблема А полиномиально сводима к проблеме 5, и пишут А ос В (см. [93]). Если проблема В является NP-полной, то А ос В для любой проблемы В € NP. Поэтому наличие некоторого эффективного алгоритма для решения NP-полпой проблемы означает существование эффективного алгоритма для произвольной проблемы из класса NP (см. [2]). Однако выполнимость соотношения A ос 3SAT сама по себе дает лишь теоретическую возможность использования алгоритмов для 3SAT при решении проблемы А.

3Constraint satisfaction problem

4 Maximum 2-satisfiability problem

Более того, хотя конструктивное доказательство теоремы Кука (см. [126]) даст явное сведение произвольной проблемы из класса NP к SAT, оно требует, чтобы исходная проблема была задана машиной Тьюринга. Поэтому его сложно использовать на практике, поскольку проблемы, которые необходимо решать, редко бывают заданы машиной Тьюринга. Для практического использования алгоритмов для 3SAT при решении некоторой проблемы А нам необходимо не только соотношение А ос 3SAT, но и подтверждение этого соотношения в виде конструктивного полиномиального алгоритма, позволяющего строить в явном виде исходные данные 3SAT по исходным данным А. Такое сведение с подтверждением называется конструктивным полиномиальным сведением [31]. Для обозначения отношения конструктивной полиномиальной сводимости мы будем использовать с�