Использование правила резолюций в вопросно-ответной процедуре транспортного планировщика

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

1. Шабанов И. А. Эволюция организационных принципов инновационного процесса / И. А. Шабанов // Вестник Инжекона. Сер. «Экономика». — СПб., 2013. — № 1 (60).

2. Шабанов И. А. Рост и развитие кадрового потенциала как фактора повышения конкурентоспособности экономики региона / И. А. Шабанов // Конкурентоспособность региональной экономики: опыт, проблемы, перспективы: материалы науч.-практ. конф. — Омск, 2007.

3. Корецкая Л. К. Механизм инновационного процесса в регионе / Л. К. Корецкая, И. А. Шабанов. — Владимир, 2005.

4. Козловская О. В. Инновационный бизнес — актуальные аспекты налогового стимулирования / О. В. Козловская, И. А. Шабанов // Потенциал российской экономики и инновационные пути его реализации: материалы науч.-практ. конф. — Омск, 2012.

УДК 656:004.83.164.2 Я. А. Селиверстов,

Федеральное государственное бюджетное

учреждение науки «Институт проблем транспорта им. Н. С. Соломенко РАН»

ИСПОЛЬЗОВАНИЕ ПРАВИЛА РЕЗОЛЮЦИЙ В ВОПРОСНО-ОТВЕТНОЙ ПРОЦЕДУРЕ ТРАНСПОРТНОГО ПЛАНИРОВЩИКА

APPLICATION OF THE RESOLUTION RULE IN THE QUESTION-ANSWER PROCEDURE OF THE TRANSPORT PLANNER

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

The article deals with the application of the resolution rule to build a deductive method of reasoning in the formulas of the first order predicate calculus with respect to question-answer procedure of the transport planner.

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

Key words: methods of automatic theorem proving, resolution rule, first-order predicate logic, question-answer procedure, intelligent transport planners, intellectualization of transport systems.

Ведение. Сложность транспортных систем и процессов в последних не раз отмечалась в [1]. Ущерб от неверных управленческих решений на транспорте в случае гибели людей невосполним. Интеллектуализация и интеллектуальное планирование [2, с. 48-56] здесь является необходимым, а потому предполагает создание интеллектуальных систем, которые наряду с точными математическими моделями [3, с. 43-50] используют данные и знания, накопленные в процессе их надлежащего функционирования [4, с. 29-43]. Таковыми являются диалоговые системы для планирования и управления на транспорте.

Выпуск 1

В

J46j

Первая вопросно-ответная система QA3 (Question Answering system, version 3), разработанная К. Грином [5] в 1969 г., основывалась на механизме доказательства теорем правилом резолюций [6], а вопросы к системе формулировались в виде формул исчисления предикатов первого порядка [7].

Применение этого правила в построении вопросно-ответных процедур мы и рассмотрим в настоящей работе.

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

Вопросно-ответная система — информационная система, способная принимать запросы и отвечать на них на естественном или формальном языке.

Выделяют два вида систем ответов на вопросы: системы общего назначения [9, р. 1-23] и системы специального назначения [10]. В системах специального назначения данные обычно относятся к специальной области и множество допустимых вопросов весьма ограничено. Системы специального назначения работают только в определенных областях (транспорт, медицина).

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

Рассмотрим на примере четыре класса вопросов в соответствии с формой ответа.

Класс 1. Вопросы, требующие ответа «да» или «нет».

Так как ответ на вопрос класса 1 — это ответ типа «да» или «нет», то задача ответа на вопрос является доказательством теоремы, где данные факты считаются аксиомами теоремы, а сам вопрос представлен как заключение этой теоремы.

Пример 1. Пусть решатель располагает информацией:

F11: Любой морской порт обслуживает морские суда.

F12: Усть -Луга — морской порт.

Запрос, который подается на вход транспортного решателя:

Q 1: Обслуживает ли морские суда Усть -Луга?

Чтобы ответить на данный запрос, необходимо доказать, что утверждение «Усть-Луга обслуживает морские суда» является логическим следствием из F и F Если последнее доказано, то ответ «да».

Решение. Пусть Р(х) и R(x) представляют соответственно предикаты «x — морской порт» и «x — обслуживает морские суда». Данные факты представляются следующими дизъюнктами:

~ P

Р

Заключение теоремы представлено дизъюнктом

R

Отрицая (1.3), выводим

~ R

Легко показывается, что дизъюнкты (1.1), (1.2) и (1.4) образуют противоречивое множество дизъюнктов. Следовательно, (1.3) является логическим следствием из (1.1) и (1.2). Таким образом, ответ должен быть «да, Усть-Луга обслуживает морские суда».

Класс 2. Вопросы, требующие в качестве ответа «где», «кто» или «при каких условиях».

Пример. Пусть решатель располагает информацией:

F21: Компания К владеет транспортным средством Т.

На вход решателя поступает запрос:

ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

МОРСКОГО И РЕЧНОГО ФЛОТА ИМЕНИ АДМИРАЛА С. О. МАКАРОВА^

Q21: Кому принадлежит транспортное средство?

Решение. Пусть P(x, у) означает <« есть владелец у». Тогда данный факт есть:

(K; T). P

Затем для ответа на наш запрос устанавливается следующее заключение:

Если доказывается, что (2.2) является логическим следствием факта (2.1), то ответ на запрос существует. Прослеживая подстановку, сделанную вместо переменной, легко установить чему равен x . Чтобы доказать эту теорему, сначала отрицаем (2.2) . Таким образом, имеем

~Р

Применяя правило резолюции к (2.1) и (2.3), выводим противоречие и теорема доказана. В

процессе применения правила x заменяется на К. Если имеет место процедура прослеживания,

то эта информация может быть выявлена и ответом будет «компания К владелец транспортного средства Т».

Очень простой способ прослеживания переменной — это добавление к дизъюнкту (2.3) предиката, называемого ANS-предикатом (от англ. answer — ответ).

Таким образом, можно записать:

~Р

Дизъюнкт (2.4) означает: «кто бы ни был владельцем транспортного средства Т, он наш ответ». Отметим, что дизъюнкт (2.4) эквивалентен формуле

На этот раз, применяя метод резолюции к (2.1) и (2.4), вместо пустого дизъюнкта мы получаем

ANS

Следовательно, наш ответ — «К-владелец Т». Легко заметить, что ANS(^) — логическое следствие дизъюнктов (2.1) и (2.4). Таким образом, первоначальная задача доказательства теоремы была преобразована в задачу вывода логических следствий.

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

Пример 3. Рассмотрим рис. 1. Пусть транспортный решатель располагает информацией:

F : Груз G расположен в месте дислокации грузов а в состоянии s

Рис. 1

F32: Существует действие ^посредством которого любой объект из места дислокации грузов а может быть перемещен в место дислокации Ь.

На вход транспортного решателя поступает запрос:

Q31: Как переместить груз из a в Ь?

Решение. Обозначим <^ находится в точке у в состоянии z» через P(x, у, z), тогда исходная информация F31 примет вид

Выпуск 1

^, a, s1). P

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

У2 действием / тогда можно считать /1 функцией, аргументами которой являются х, у1, у2, г. Значением /1(х, у1, у2, г) является новое состояние, которое возникает после того, как х, находившейся первоначально в состоянии г, передвинут из у1 в у2 действием/ Это записывается формулой

Используя (3.1) и (3.2), решатель в состоянии ответить на запрос 031. Запишем два дизъюнкта, представляющих исходные факты:

~Р

Дизъюнкт

~Р

представляет поступивший запрос.

Из (3.3) и (3.4) порождается резольвента (3.6):

Р

Из (3.5) и (3.6) порождается резольвента (3.7):

АЖ

Таким образом, ответ на запрос состоит из одного действия — применения /1 для перемещения груза G из а в Ь.

Класс 4. Вопросы, включающие проверку условий (ветвление).

Пример 4. Решатель обладает информацией:

Р41: Если вес груза G меньше М, его перевозка должна осуществляться транспортным средством Т1.

ГАТ Если вес груза G не меньше М, его перевозка должна осуществляться транспортным средством Т2.

На вход решателя поступает вопрос:

041: Каким транспортным средством осуществлять перевозку груза G?

Решение: Пусть Р(х) и Я(х, у) означают соответственно «вес груза х меньше М» и «перевозка груза х должна осуществляется транспортным средством у». Тогда мы имеем

-Р^Р^Г1),

Р

Нашему запросу соответствует дизъюнкт

~Д

Из (4.1)-(4.3) порождаются следующие резольвенты:

— из (4.1) и (4.3) ^ (4.4):

т

— из (4.2) и (4.3) ^ (4.5):

— из (4.4) и (4.5) ^ (4.6):

-Р^уЛЛ/^Г1);

P

АШ

В дизъюнкте (4.6) сообщается, что перевозка груза О должна осуществляться либо транспортным средством Т1, либо транспортным средством Т2. Очевидно, что выводимый из дизъюнкта (4.6) ответ неудовлетворительный. Необходимо установить, при каком условии перевозка груза

О должна осуществляться транспортным средством Т1 и при каком условии — транспортным средством Т2.

Так как дизъюнкт (4.6) имеет вид ЛЫБ(Т 1)^ЛЫ8(Т2), задается следующий вопрос: «При каком условии будет истинно ЛЫБ(Т')?», или «При каком условии ЛЫБ(Т') будет логическим следствием дизъюнктов (4.1)-(4.3)?» Аналогичный вопрос задается для дизъюнкта ЛЫБ(Т2).

Вывод дизъюнкта (4.6) представлен на рис. 2, где каждый узел соответствует дизъюнкту, участвующему в выводе, а переменные в дизъюнктах, приписанных исходным узлам, переименованы таким образом, что дизъюнкты не имеют общих переменных.

-ШС. х) V АЖ

Рис. 2. Дерево Т0

Обозначим это дерево вывода через Т0. Проанализируем Т0 с помощью алгоритма извлечения информации.

Алгоритм извлечения информации.

Шаг 1. Пусть дизъюнкт С в дереве Т0 есть резольвента дизъюнктов С1 и С2 с отрезаемыми литерами соответственно Ь и Ь пусть 0 — наиболее общий унификатор литер Ь и ~ Ь

Тогда на ребре, ведущем от С. к С, / = 1, 2, напишем отрицание литеры Ь0 и подстановку 0. (Если 0 — пустая подстановка, то напишем только отрицание.) В рассматриваемом примере дизъюнкт (4.4) — резольвента дизъюнкта (4.3) и дизъюнкта (4.1). Отрезаемая литера в (4.3) — это !{((/. х). Наиболее общий унификатор отрезаемых литер — {ТЧх}.

-ШО. х) V АШх) '-Р

3 У

[149

А^СТ1) УАМЭСТ2)

Рис. 3. Дерево Т1

Поэтому мы приписываем Я(0; Т') и подстановку {х ^ Требру, ведущему от (4.3) к (4.4). Аналогично мы добавляем ~Я(0; Т') и подстановку {х ^ Т'} к ребру, ведущему от (4.1) к (4.4) . Проделав данную процедуру для остальных ребер, мы получим дерево Тр изображенное на рис. 3.

Рис. 4. Дерево Т2

Шаг. 2. Перевернем дерево Т добавим стрелки к ребрам и выбросим все дизъюнкты, приписанные узлам. В итоге получим дерево Т2, изображенное на рис. 4, где все висячие узлы помечены.

Шаг. 3. В дереве Т2 удалим все узлы (и связанные с ним ребра), соответствующие дизъюнктам, не содержащим предиката ЛЫБ. В рассматриваемом примере будут удалены В, С и связанные с ними ребра, так как дизъюнкты (4.1) и (4.2) не содержат предиката ЛЫБ. Результирующее дерево Т3 представлено на рис. 5.

А>Ъ

Рис. 5. Дерево Т3 Рис. 6. Дерево Т4

Шаг 4. Пусть Ы N ..., Ыт — висячие узлы дерева Т Для каждого Ы , і = 1, 2, ..., т, пусть

1(Ы) обозначает конъюнкцию литер, приписанных пути от самого верхнего узла к N.. Пусть С(Ы) — дизъюнкт, соответствующий узлу Ы. Находим в дизъюнкте ответа литеру Ь(Ы) такую, что Ь(Ы.) — логическое следование конъюнкции 1(Ы ) Л С(Ы.). Припишем Ь(Ы.) к узлу N..

В нашем примере С(Л) = ~ Я(0, х) V ЛЫБ (х) и Ь(Л) = ЛЫБ(Т1), так как 1(Ы ) = Р(О) Л R(G, Т1). Аналогично легко видеть, что Ь(В) = ЛЫБ(Т2). Полученное таким образом дерево Т4 изображено на рис. 6.

Шаг 5. Запишем в виде Ы1, Ы2, ., Ы список всех узлов дерева Т4 таких, что из Ы, 1 < . < д, ведет только одно ребро а.. Пусть Ь(а .) — литера, приписанная ребру а.. Удалим из дерева Т4 литеры Ь(а), 1 <. < д, и обозначим результирующее дерево через Т5. Для рассматриваемого примера Т5 представлено на рис. 7.

ВЕСТНИКД

ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ЩАЫ “

МОРСКОГО И РЕЧНОГО ФЛОТА ИМЕНИ АДМИРАЛА С. О. МАКАРОВА

ANSfT1) ANSfT2)

Рис. 7. Дерево Т5

Заметим, что рис. 7 целесообразно рассматривать как дерево решений. Если истинно P(G), то истинно А^(Г). В противном случае истинно ANS(T2). Таким образом, решатель выводит следующий ответ на запрос Q41: «Если вес груза G меньше M, его перевозка должна осуществляться транспортным средством Т1. В противном случае транспортировка должна осуществляться транспортным средством Г2».

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

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

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

1. Белый О. В. Архитектура и методология транспортных систем / О. В. Белый, О. Г. Кокаев, С. А. Попов. — СПб.: Элмор, 2002. — 256 с.

2. Скороходов Д. А. Принципы построения системы информационной поддержки для принятия решений в аварийных ситуациях / Д. А. Скороходов, А. Л. Стариченков // Морские интеллектуальные технологии. — 2009. — № 1 (3).

3. Селиверстов Я. А. Моделирование процессов распределения и развития транспортных потоков в мегаполисах / Я. А. Селиверстов // Известия ЛЭТИ. — 2013. — № 1.

4. Фахми Ш. С. Адаптация космической телевизионной системы к этапам наблюдения объекта / Ш. С. Фахми [и др.] // Вопросы радиоэлектроники. — 2012. — № 1.

5. Green C. The Application of Theorem Proving to Question-Answering System / C. Green. — N. Y.: Garland Publishing, 1969. — 21 p.

6. Чень Ч. Математическая логика и автоматическое доказательство теорем / Ч. Чень. — М.: Наука, 1983. — 360 с.

Выпуск 1

7. Такеути Г. Теория доказательств / Г. Такеути. — М.: Мир, 1978. — 417 с.

8. Ефимов Е. И. Решатели интеллектуальных задач / Е. И. Ефимов. — М.: Наука, 1982. —

320 с.

9. Quarteroni S. Designing an Interactive Open-Domain Question Answering System / S. Quar-teroni, S. Manandhard. — Cambridge: Cambridge University Press, 2008.

10. Hai Doan-Nguyen. Improving the Precision of a Closed-Domain Question-Answering System with Semantic Information / Doan-Nguyen Hai, L. Kosseim. — Quebec, 2004. — 10 p.

УДК 339.9 О. В. Малиновская,

д-р экон. наук, профессор, ГУМРФ имени адмирала С. О. Макарова;

И. П. Скобелева,

д-р экон. наук, профессор, ГУМРФ имени адмирала С. О. Макарова

РАЗВИТИЕ ИНФРАСТРУКТУРНЫХ ОБЛИГАЦИЙ В ТРАНСПОРТНОМ СЕКТОРЕ РОССИИ: НОРМАТИВНО-ПРАВОВОЙ КОНТЕКСТ И ЕГО ПРИМЕНЕНИЕ

DEVELOPMENT OF INFRASTRUCTURE BONDS IN THE TRANSPORT SECTOR IN RUSSIA: THE LEGAL CONTEXT AND ITS APPLICATION

Статья посвящена проблемам правового развития инфраструктурных облигаций как инновационного инструмента финансирования ГЧП-проектов на транспорте. В ней также представлена характеристика мирового опыта развития этого инструмента финансирования ГЧП-проектов в транспортной отрасли.

The article is devoted to the problems of legal development of infrastructure bonds as an innovative financing instrument PPP projects in transport. It also presents the characteristics of world development experience of this financing instrument of PPP projects in the transport sector.

Ключевые слова: государственно-частное партнерство, инфраструктурные облигации, транспорт, концессия.

Key words: public-private partnerships, infrastructure bonds, transportation, concession.

В

152]

И

НСТИТУТ государственно-частного партнерства (ГЧП), прочно вошедший в практику развития транспорта на глобальном экономическом пространстве и получивший значительное развитие в России, сегодня требует становления инновационных источников финансирования, необходимых для собственного развития в России. Тренд на привлечение «длинных» денег на развитие инвестиционного процесса в транспортной отрасли начал формироваться еще в период нулевых годов и приобрел особую актуальность в период финансового кризиса как действенный фактор обеспечения стимулирования экономического роста. Сегодня развитие института ГЧП в России находится на новом этапе развития и обозначается как этап создания рынка инфраструктурных проектов прежде всего в транспортной отрасли, который характеризуется в мировой практике как этап развития новых инструментов финансирования этого рынка.

Таким образом, появление инфраструктурных облигаций как инструмента финансирования отраслевых ГЧП-проектов — процесс, предопределенный развитием института ГЧП.