Глава 4. Автоматическое планирование и принятие решений
Глава 4. Автоматическое планирование и принятие решений
Описанные ниже события могли произойти в любой день.
14:32 — грузовик, двигавшийся по второстепенной дороге с превышением скорости, перевернулся. Водитель получил сильный ушиб головы.
14:53 — на место аварии прибыли пожарные и скорая помощь, которые за несколько минут извлекли из машины водителя в бессознательном состоянии и с серьезной черепно-мозговой травмой.
15:09 — машина скорой помощи прибыла в больницу, где реаниматологи диагностировали смерть мозга водителя.
15:28 — была установлена личность водителя, о его смерти сообщили родственникам.
16:31 — группа психологов связалась с семьей погибшего, чтобы оказать эмоциональную поддержку и получить согласие на передачу донорских органов, не пострадавших при аварии.
16:36 — после непродолжительных споров родственники согласились передать врачам почки умершего (далее — донора).
16:48 — бригада хирургов начала удаление почек и их обследование. Параллельно с этим администрация больницы улаживала необходимые бюрократические формальности.
17:24 — после завершения операции в информационную систему были введены биологические данные донора и характеристики его органов.
Так начинается трансплантация органов.
Как происходит трансплантация
17:24 — информационная система мгновенно определила двух реципиентов донорских почек, отправила им уведомление и выделила необходимые ресурсы для перевозки. В первом случае для перевозки почки в соседний город на расстояние 30 километров потребовалось подготовить машину скорой помощи. Во втором случае почка была доставлена самолетом в город, находящийся в 450 километрах, где действовала иная автономная медицинская система. Перевозка второй почки из больницы в ближайший аэропорт была произведена на вертолете. Все необходимые мероприятия были проведены информационной системой автоматически. Одновременно с этим система выполнила большую часть юридических процедур в соответствии с требованиями систем здравоохранения в городах донора и реципиента.
18:10 — началась первая операция по пересадке почки в больнице соседнего города.
19:03 — началась вторая операция в городе, расположенном в 450 километрах.
21:00 — оба реципиента получили необходимые лекарства и иммунодепрессанты.
Обе операции прошли успешно.
Почему испанская система пересадки донорских органов считается одной из лучших в мире? Какие особенности этой системы отличают ее от систем других стран с более высоким уровнем развития науки и техники? Почему Европейская комиссия рассматривает возможность внедрения испанской модели во всех странах Евросоюза? Как уже читатель наверняка догадался, испанская процедура трансплантации основана на мощной интеллектуальной системе, доступ к которой имеют все больницы страны. Эта система не только учитывает потребности и характеристики каждого реципиента и все логистические детали, но также сложность и неоднородность правовых норм, связанных с пересадкой органов, в разных регионах.
Указанная интеллектуальная система состоит из множества относительно простых узкоспециализированных информационных систем, формирующих мощный «коллективный разум» (так называемая многоагентная система). Именно поэтому Испания в сфере трансплантации органов занимает первое место в мире. Система координирования трансплантации, как правило, имеет многоуровневую структуру, в которой выделяются национальный, зональный, региональный уровни и отдельные больницы. На уровне отдельных больниц данные реципиентов могут распределяться по сети больниц или же содержаться в централизованном хранилище данных.
В силу указанных выше особенностей существует множество интеллектуальных агентов, управляющих информацией обо всех реципиентах. С этими агентами непрерывно обмениваются данными другие интеллектуальные агенты, которые задействуются всякий раз, когда становятся доступны донорские органы. Другие агенты системы занимаются самыми разными аспектами, к примеру планируют и распределяют логистические ресурсы для перевозки органов или решают административные вопросы согласно требованиям различных региональных систем здравоохранения.
* * *
ГОЛУБИНЫЙ РЕЙТИНГ
Известнейшая компания Google пользуется огромным авторитетом в мире компьютерных технологий и искусственного интеллекта. Священный Грааль Google — алгоритм, используемый для ранжирования результатов поиска, к которому несколько миллионов раз в секунду обращаются пользователи со всего мира. Этот алгоритм привлек огромный интерес, и в Google поступило столько обращений с просьбами опубликовать его, что утром 1 апреля 2002 года на главной странице поисковика была размещена ссылка, которая вела на описание алгоритма ранжирования. Этот алгоритм назывался pigeon ranking («голубиный рейтинг»), и такое название было выбрано не случайно. В статье, расположенной по ссылке, объяснялось, что Google располагал установками, заполненными PC (от английского pigeon cluster — «голубиный кластер»; это же сокращение обозначает «персональный компьютер»). Перед каждым голубем находились экран и клавиатура. В описании алгоритма указывалось, что всякий раз, когда пользователь вводит запрос в Google, все сайты, удовлетворяющие поисковому запросу, отображаются перед одним из голубей, который затем начинает клевать кнопки на клавиатуре. После этого сайты упорядочиваются в зависимости оттого, сколько раз голубь нажмет на кнопки.
В этой же статье объяснялось, как Google работает с голубями, как они живут и в каких условиях содержатся. Также упоминалось, что в Google пробовали использовать других пернатых, в частности кур и хищных птиц, но больше всего для выполнения задачи подошли именно голуби.
Автор статьи даже осмелился указать, что пусть ни один голубь еще не стал членом Конституционного суда, была доказана их эффективность как авиадиспетчеров и футбольных арбитров.
Многие инженеры и конкуренты Google не сразу поняли, что статья была опубликована 1 апреля — в День смеха, который отмечается в многих странах, в том числе в США.
* * *
Упрощенный пример сети агентов, отвечающей за координацию перевозки органов.
Подобная многоагентная интеллектуальная архитектура обладает множеством преимуществ. В частности, эта система является отказоустойчивой — если один или сразу несколько агентов откажут, система будет по-прежнему способна решать задачи за счет саморегулирования и задействования других агентов. Еще одно важное преимущество подобной архитектуры заключается в использовании относительно простых, но узкоспециализированных агентов, на основе которых можно выстроить интеллектуальную систему, способную за несколько секунд решать сложные междисциплинарные задачи.
* * *
АГЕНТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ
Компьютерное программирование — быстро развивающаяся дисциплина. На сегодняшний день существует пять больших семейств языков программирования, наиболее популярным из которых является семейство объектно-ориентированных языков. В объектно-ориентированном программировании все сущности представлены с помощью особых единиц информации, называемых объектами. Объекты имеют ряд атрибутов, где хранят информацию о самих себе, и способны выполнять с этой информацией некоторые операции. Объектно-ориентированное программирование требует вмешательства координаторов, которые обладают интеллектом и постоянно направляют запросы тем или иным объектам при решении задач. Неизменно предполагается, что объект — это элемент, не обладающий интеллектом, который ожидает указаний. Но не так давно мощное развитие получило новое направление программирования — агентно-ориентированное. В нем «неразумные» объекты превращаются в намного более интеллектуальные и автономные агенты, и одновременно снижается роль координатора.
Планирование — основа всего
Планирование использования ресурсов для успешного решения тех или иных задач может оказаться крайне сложным даже для опытного человека. Такое планирование используется во всех областях, начиная от не слишком важных задач, например планирования учебного расписания, распределения аудиторий, лабораторий и аудиовизуальных материалов, и заканчивая крайне важным планированием ресурсов при тушении лесных пожаров или борьбе с другими стихийными бедствиями.
Автоматические рассуждения крайне просты для человека, но невероятно сложны для машин. По сути, способность рассуждать в немалой степени является отличительным признаком людей, и ключевые особенности рассуждений до сих пор не слишком понятны нейробиологам. Для имитации рассуждений человека инженеры разработали ряд очень интересных приемов, которые применяются, к примеру, при тушении лесных пожаров.
Сегодня многие пожарные службы используют системы планирования с искусственным интеллектом. Как правило, при обнаружении лесного пожара средних размеров специалисту экстренной службы требуется до полутора часов на разработку плана тушения. Этот план подробно описывает все действия, которые следует выполнять всеми доступными средствами в зависимости от характеристик местности, погодных условий и так далее. Однако специалисты часто сталкиваются со следующей проблемой: условия в районе пожара непрерывно меняются, и этот процесс идет так быстро, что человек попросту не успевает изменить план действий. В результате многие службы пытаются внедрить автоматизированные системы, способные составить план тушения пожара за несколько секунд. Система фиксирует такие параметры, как рельеф местности, погодные условия, проезды к зоне пожара, доступные авиационные и наземные средства, а также возможность координировать действия с другими подразделениями и центрами управления, на основе этих параметров она составляет план и отправляет его на проверку человеку-эксперту.
Тушение лесного пожара требует координирования многочисленных человеческих и материальных ресурсов.
Может случиться так, что в данный момент одна единица техники не задействована, и система предлагает два варианта: перевести ее в зону, где бушует пожар, либо отправить ее на тушение очагов пожара в другую, менее опасную область, расположенную ближе. Как система определит, какой из вариантов лучше? Логично, что конечная цель — потушить пожар, следовательно, кажется более естественным направить технику туда, где пожар сильнее. С другой стороны, на переброску тех ники может уйти несколько часов, а всего в нескольких минутах езды очаги пожара не представляют большой опасности, и их можно потушить относительно легко.
Как объективно оценить преимущества от тушения пожара в определенной области с учетом расстояния до нее и затраченного времени? Именно такой оценки требует классическая, неинтеллектуальная система планирования. Но при тушении пожара используется не одна, а несколько десятков единиц наземной и воздушной техники.
Также можно учесть новые переменные, например скорость ветра и прогноз погоды, возможные дожди, расположение жилья, природоохранных зон и так далее. При таком обилии переменных становится понятной огромная потребность в интеллектуальной системе, способной принимать решения с учетом всех перечисленных факторов и на основе нечетких параметров.
* * *
НЕЧЕТКАЯ ЛОГИКА
Нечеткая логика — раздел математической логики, приближающий логические действия и методы к естественным, человеческим рассуждениям. Как правило, в реальной ситуации ничто не делится на белое и черное, но в классической логике, в частности в булевой, переменные могут быть только истинными или ложными, что вынуждает рассматривать лишь крайности.
К примеру, на вопрос, хорошо или плохо играет вратарь футбольной команды из первого дивизиона чемпионата Казахстана, дать однозначный ответ нельзя: в сравнении с элитой мирового футбола он наверняка не слишком хорош, но по сравнению с вратарем моей районной команды он будет первоклассным игроком.
Поэтому переменные нечеткой логики принимают значения не «истина» или «ложь», а вещественные значения, заключенные на интервале от 0 до 1, где значению 1 соответствует «истина», 0 — «ложь». Если мы обозначим через 0 неспособность отразить любой удар, а через 1 — уровень лучшего вратаря мира, то вратарь казахской команды получит вполне достойную оценку в 0,73.
* * *
Для решения задач такого типа обычно используются классические алгоритмы поиска, применяемые в искусственном интеллекте, в частности поиск с возвратом (back-tracking) или метод ветвей и границ (branch-and-bound). Оба этих алгоритма действуют схожим образом: по сути, они разворачивают комбинаторное дерево и обходят его в поисках оптимального варианта. Развертывание комбинаторного дерева происходит достаточно просто. На первом этапе создается дерево, содержащее все возможные планы (вспомните понятия, которые мы объяснили в первой главе, рассказывая об интеллектуальном алгоритме, способном определять оптимальные ходы в шахматной партии). Далее с помощью интеллектуальных алгоритмов последовательно отсекаются те ветви, которым соответствуют нереальные планы либо планы, нарушающие ограничения или ведущие к неоптимальному решению.
Важное отличие метода поиска с возвратом от метода ветвей и границ заключается в том, что первый метод состоит в обходе дерева в глубину, второй — в обходе в ширину. Это различие крайне важно: в зависимости от представления задачи отсечение той или иной ветви может иметь разную эффективность.
Последовательное отсечение ветвей дерева по мере обхода абсолютно необходимо — в противном случае, как и почти во всех комбинаторных задачах, число планов, а значит, и число ветвей, будет так велико, что его нельзя будет обойти за разумное время. Чтобы ускорить отсечение ветвей, в методах, основанных на обходе дерева, обычно используются так называемые эвристики (или формальное представление интуитивных понятий), которые может применить специалист предметной области, чтобы определить: та или иная ветвь не приведет к нужному результату, и ее необходимо отсечь как можно скорее. Разумеется, если мы отсечем ветвь, которая соответствует неосуществимому плану, на раннем этапе алгоритма, то можем сэкономить несколько часов вычислений — с переходом на более высокие уровни число вариантов, которые необходимо проанализировать, возрастает экспоненциально.
Простой пример дерева планирования для игры «крестики-нолики».
* * *
ТЕОРЕМА «БЕСПЛАТНОГО ОБЕДА НЕ БЫВАЕТ»
Теорема под названием «бесплатного обеда не бывает» (no-free lunch) гласит: не существует алгоритма, позволяющего получить оптимальные решения всех возможных задач. Теорема получила свое любопытное название на основе метафоры о стоимости блюд в различных ресторанах. Допустим, что существует определенное число ресторанов (каждый из них обозначает определенный алгоритм прогнозирования), где в меню различным блюдам (каждое блюдо обозначает определенную задачу прогнозирования) сопоставлена цена (или качество решения этой задачи, которое позволяет получить рассматриваемый алгоритм). Человек, который любит поесть и при этом не прочь сэкономить, может определить, какой ресторан предлагает его любимое блюдо по самой выгодной цене. Вегетарианец, сопровождающий этого обжору, наверняка обнаружит, что его любимое вегетарианское блюдо в этом ресторане стоит намного дороже. Если обжора захочет полакомиться бифштексом, он выберет ресторан, где бифштекс подают по самой низкой цене. Но у его друга-вегетарианца при этом не останется другого выбора, кроме как заказать единственное вегетарианское блюдо в этом ресторане, пусть даже по заоблачной цене. Это очень точная метафора ситуации, когда необходимость использования определенного алгоритма для решения конкретной задачи приводит к гарантированно неоптимальным результатам. Исследователи прилагают огромные усилия для создания супералгоритма или суперметода, позволяющего составить идеальный план, но в конечном итоге неизменно сталкиваются с определенным множеством данных или контекстом, в котором оптимальные результаты показывает другой алгоритм.
Теорема имеет еще одно важное следствие: если мы тратим много сил на корректировку алгоритма, чтобы добиться идеальных результатов для определенных исходных данных, эти корректировки гарантированно приведут к ухудшению работы алгоритма для другого множества данных. Вывод: любой алгоритм будет либо работать идеально для небольшого числа случаев и плохо — во всех остальных, либо будет демонстрировать посредственные результаты во всех случаях. соответствует неосуществимому плану, на раннем этапе алгоритма, то можем сэкономить несколько часов вычислений — с переходом на более высокие уровни число вариантов, которые необходимо проанализировать, возрастает экспоненциально.
Выявление конфликтов
Остров Кипр, Средиземное море, январь 1997 года. Власти Кипра и Греции объявили об установке двух зенитно-ракетных комплексов С-300 класса «земля-воздух», закупленных в России, что стало серьезным усилением вооруженных сил обоих государств в рамках единого оборонного пространства.
Представители российского министерства обороны подтвердили, что переданные Кипру комплексы С-300 предназначены для выполнения исключительно оборонительных задач и никак не нарушат неустойчивый баланс сил между греческими и турецкими военными на острове.
Зенитно-ракетный комплекс С-300 на военном параде в России..
Турция, январь 1997 года. Турецкое правительство незамедлительно заявило, что установка ракет является серьезной угрозой безопасности страны, и объявило о принятии встречных мер. Кроме того, турецкие власти сообщили, что если ракеты коснутся кипрской земли, то это станет сигналом к началу военных действий на острове.
В ответ правительство Кипра перевело вооруженные силы в режим максимальной боевой готовности, который был снят лишь в июне того же года.
Весна 1997 года. Греческое правительство, в свою очередь, сочло, что установка ракет С-300 не поможет сдержать турецкую угрозу, так как ракеты были открыты для удара турецких войск и не уцелели бы в случае нападения. Следовательно, власти Греции посчитали, что любые попытки дестабилизировать ситуацию в регионе будут предприняты турецкой стороной, так как комплексы С-300 применяются исключительно для обороны.
В этот же период была проведена мобилизация греческой армии для поддержки кипрских войск на случай атаки со стороны Турции. Российские власти сохраняли нейтралитет, однако заявили, что на продажу двух комплексов С-300 не повлияет какое-либо вмешательство извне.
Турция начала интенсивные переговоры с союзниками по НАТО, но безуспешно. Затем турецкие власти решили начать сотрудничество с Израилем и обучить войска противодействию комплексам С-300.
Нестабильный регион в Восточном Средиземноморье.
Сентябрь 1997 года. Турецкий военный флот начал рейды в Восточном Средиземноморье с целью обнаружения судов, в частности российских военных кораблей, чтобы предотвратить доставку ракет. Россия и Греция оповестили Турцию о начале военных действий в случае атаки или морской блокады Кипра.
Декабрь 1997 года. Россия сосредоточила значительные военно-морские силы в регионе, в том числе авианосцы и подводные лодки. Предположительно их задачей была перевозка комплексов С-300 и уничтожение турецкого флота в случае попытки перехватить груз.
Январь 1998 года. Под давлением США и Великобритании и перед лицом турецкой угрозы власти Греции в итоге решили отказаться от установки ракет на Кипре. Ракеты С-300 были размещены на греческом острове Крит, а на Кипр были доставлены другие, менее мощные комплексы, переданные греческими властями правительству Кипра в обмен на С-300.
Результатом конфликта, который мог завершиться трагически и иметь самые серьезные последствия, стала дестабилизация отношений между Турцией и Кипром. Позиции греческого правительства, напротив, не пострадали.
Какую роль в этих событиях сыграл искусственный интеллект? Как можно предсказать и даже предотвратить тактические маневры, чтобы избежать угрозы начала военных действий, как в описанной ситуации? В 2005 году группой исследователей Кипрского университета была разработана сложная интеллектуальная система, основанная на нечетких когнитивных картах. При обучении системы использовались эволюционные алгоритмы, способные с высокой точностью предсказывать и моделировать политическую нестабильность. Эта система при анализе кипрского конфликта выделяет 16 переменных, начиная от «нестабильности/напряженности на Кипре» и заканчивая «влиянием международного сообщества». Кроме того, рассматриваются такие переменные, как «политическая поддержка со стороны Греции» или «усиление турецкой армии».
Нечеткая когнитивная карта — это нейронная сеть, в которой каждый нейрон показывает, как изменяется значение одной из переменных с течением времени.
К примеру, в определенный момент политическая поддержка со стороны Греции может быть довольно велика, и нейрон, соответствующий этой переменной, может содержать значение 92 %. Нейрон, соответствующий переменной «усиление турецкой армии», может содержать невысокое значение, к примеру 23 %.
С другой стороны, каждый нейрон связан с соседними с помощью ребер. Каждое ребро описывает вес причинно-следственной связи между нейронами, которые оно соединяет. К примеру, «политическая нестабильность на Кипре» влияет на «усиление турецкой армии» с величиной 0,32. Если политическая нестабильность в определенный момент составляет 50 %, это вызовет прямое усиление турецкой армии на 16 %, то есть на 0,32 ? 50 %. Также существуют отрицательные причинно-следственные связи: к примеру, переменная «решение Кипрского вопроса» влияет на переменную «политическая нестабильность на Кипре» с величиной —0,21.
Сложные причинно-следственные связи между нейронами системы (ее когнитивная карта содержит 45 связей) зафиксированы эволюционным алгоритмом, в котором каждая особь популяции представляет собой матрицу весов для 45 связей между переменными карты. Приспособленность каждой матрицы оценивается по тому, насколько точно она описывает эскалацию конфликтов, произошедших в прошлом.
Таким образом, после обучения системы с помощью подходящей матрицы весов исследователи смогли моделировать ситуации вида «что будет, если…» для поиска оптимального решения Кипрского вопроса. В статье, опубликованной авторами системы, было рассмотрено три сценария, на примере которых описывались прогнозы, составленные системой. В одном из случаев была рассмотрена ситуация, при которой турецкая армия навсегда покидала остров. Прогноз включал различные события, приводившие к постепенному росту напряженности, за которым в итоге следовали анархия и хаос.
* * *
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И ВОЙНЫ
В истории человечества войны были ключевым фактором технического прогресса во все времена, начиная с изготовления Архимедом военных машин во время Пунических войн и заканчивая развитием ядерной энергетики в период холодной войны.
Искусственный интеллект также изначально имел военное применение. Сами основы вычислительной техники были заложены в разгар Второй мировой войны, когда союзникам потребовалось расшифровать секретные коды нацистских войск.
Во время холодной войны важные открытия в этой области произошли из-за того, что требовалось перевести огромный объем научно-технических текстов с русского языка на английский, и для выполнения автоматического перевода появились техники обработки естественных языков.
В 1966 году был опубликован доклад Комитета по автоматической обработке языков (ALPAC — от англ. Automatic Language Processing Advisory Committee), в котором рекомендовалось прекратить государственное финансирование исследований, связанных с обработкой естественного языка. В качестве причины указывались неудовлетворительные результаты, полученные за 10 лет исследований.
Рассказывают (хотя вряд ли эти данные можно считать достоверными), что во время войны в Персидском заливе американские военные систематически производили бомбардировки всех целей, где, по оценкам интеллектуальной системы, были спрятаны самолеты противника.
По-видимому, решения принимались с помощью так называемых нейронных сетей Кохонена, о которых будет рассказано далее.
Машина «Энигма», применявшаяся во время Второй мировой войны для шифрования и расшифровки сообщений.