Искусственный интеллект. Краткая история будущего - Тоби Уолш

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

Представим, что роботу поручили решить головоломку «Ханойская башня». Эта перестановочная головоломка состоит из трех стержней, на которые надеты несколько дисков разного диаметра. Изначально все диски расположены на левом стержне, самый большой диск находится внизу, а самый маленький вверху. Цель – переместить и расположить все диски в том же порядке на правом стержне. В процессе решения головоломки игрок может передвигать за раз только один диск. Каждый шаг – это перенос верхнего диска с одного стержня на верх другого. Чтобы усложнить задачу, игроку нельзя класть больший диск на меньший, только меньший на больший.

Решения «Ханойской башни» достаточно сложны. Если в головоломке только два диска, игрок берет меньший из них с левого стержня и оставляет на пустом стержне посередине. Затем переносит большой диск с левого на пустой правый стержень.

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

Это не так уж и сложно, пока есть всего два диска. Чем больше дисков, тем запутаннее и сложнее становится решение. С тремя дисками требуется семь шагов, чтобы решить головоломку, с четырьмя дисками – 15 шагов, с пятью – 31 шаг, а с шестью – 63 шага. С каждым прибавлением всего одного диска общее количество шагов увеличивается больше чем вдвое. Математики называют это комбинаторным взрывом.

Так как же STRIPS решает проблемы? Данные головоломки представлены набором математических истин “on(disc2,peg1)” и “on(disc1,disc2)”. Следовательно, в исходном значении большой диск, обозначенный disc 2, расположен на левом стержне peg 1, тогда как маленький диск disc 1 располагается сверху большого disc 2. Получается, что конечная цель “on(disc2, peg3)” и “on(disc1,disc2)”. Следовательно, большой disc 2 должен находиться на правом стержне peg 3, а маленький disc 1 поверх большого disc 2. Существует набор математических операторов для преобразования одного состояния в другое. Например, одним шагом оператор может преобразовать “on(disc1,disc2)” в “on(disc1,peg2)”, передвинув маленький disc 1, расположенный на большом disc 2, на средний стержень peg 2.

«Ханойская башня» окружена множеством мифов. Один из них заключается в том, что эта головоломка пришла к нам из древнеиндуистского храма Каши Вишванатх. На трех потертых столбах в одном из помещений храма были нанизаны 64 золотых диска. Сотни лет брахманы передвигали диски с одного столба на другой. Задача была сродни подвигам Геракла. Если бы монахи перемещали один диск каждую секунду, то им понадобилось бы около 600 миллионов лет, чтобы достигнуть цели[32]. К счастью для человечества, легенда также гласит, что, когда монахи решат эту головоломку, наступит конец света.

Настоящее происхождение «Ханойской башни» куда прозаичнее. Игру придумал французский математик Эдуард Люка[33] в 1889 году как один из способов увлекательного времяпрепровождения. До 1956 года эта игра поистине бросала вызов роботам, пока мы не начали создавать таких роботов, как Шейки.

Что действительно сделало STRIPS эффективным и могущественным, так это разделение математического описания задачи от описания ее решения. Такое разделение содержания проблемы от ее решения стало одной из главных особенностей эры символизма. Мы отделили что от как. Чтобы STRIPS решил новую задачу, мы просто меняем что, а не как. Добавить еще один диск на «Ханойскую башню»? Не проблема. Просто меняем описание задачи и добавляем еще один диск. Два диска одного размера? Снова не проблема. Просто меняем описание задачи.

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

Например, одно из различий между исходным и целевым состояниями «Ханойской башни» заключается в том, что самый большой диск нанизан не на тот стержень. Исходное состояние – на левом стержне “on Peg 1”. Конечное состояние – на правом стержне “on Peg 3”. Анализ средств и целей предполагает, что нам необходимо переместить самый большой диск с исходного стержня на конечный. Это подразумевает новую подцель – переместить любой диск, находящийся над самый большим, таким образом, что мы сможем его высвободить и переместить на конечный стержень. Затем мы рекурсивно применяем анализ средств и целей к этой подцели – освобождению самого большого из оставшихся дисков, что позволит убрать с пути диски меньшего размера.

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

ПОИСКОВЫЕ ОГРАНИЧЕНИЯ

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

Экспоненты становятся запредельно большими. Знаменитая притча об изобретении шахмат поможет понять, какие проблемы возникают у искусственного интеллекта в этом случае. Жил на свете человек, и создал он шахматы, которые захотел показать императору Индии. Император был настолько поражен и благодарен, что предложил изобретателю самому выбрать награду, ожидая, что он попросит золото или другие богатства. Изобретатель же попросил всего лишь рис.

«Император, мои желания очень просты. Я хотел бы только одного. Дайте мне одно рисовое зернышко за первую клетку шахматной доски, два зернышка – за вторую клетку, четыре зернышка – за следующую, восемь – за следующую и так далее за все 64 клетки».

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