Плэнер — язык логического программирования для ИИ: что из него получилось

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

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

Плэнер разработан в Лаборатории искусственного интеллекта Массачусетского технологического института Карлом Хьюттом в 1967—1971 годы. Изначально он позиционировался как язык для автоматического планирования и диспетчеризации в робототехнике. Но потом получил признание как язык с наиболее адекватным набором выразительных средств для задач ИИ.

Например, в оригинальной статье Хьютта приводятся такие примеры функции assign, где первый аргумент приводится в соответствие со вторым аргументом:

{prog ((a ptr) (h atom) (c seg))
	{assign? ($_a k $_h $_c) ((1) k b 1 a)}}
	a gets the value (1)
	h gets the value b
	c gets the value -1 a-

{prog ((c seg) (h atom) (a ptr))
	{assign? ($_c $_h k $_a) (a l b k q ) ) )
	c gets the value -a 1-
	h gets the value b
	a gets the value q

{prog ((first ptr) (middle seg) (last ptr))
	{assign ? ($_first$_middle$_last) (1,2,3,4)}}
	first gets the value 1
	middle gets the value -2 3-
	last gets the value 4

{prog ((a ptr) (b ptr))
	{assign? ($_^$_b) (d) }} fails because there
is only one element in (d) .

{prog (( a atom))
	{assign? $_a (1 2)}} fails because (1 2)
is not an atom.

В статье отмечается, что в этой реализации Плэнера используется язык Matchless, ныне практически забытый. Статья Хьютта с описанием языка опубликована в журнале Proceedings of the 1st International Joint Conference on Artificial Intelligence. — 7—9 May 1969. — P. 295—302.

Можно посмотреть ещё один пример логического программирования из статьи о языке Picat (о нём ниже):

ain =>
  Arr = [a, b, c, a],
  X = a,
  member(X, Arr),
  member(Y, Arr),
  X != Y,
  println([X, Y]).

Здесь интересным моментом является значение Y, которое Picat находит в ходе выполнения, чтобы удовлетворить условиям программы.

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

Хотя язык так и не реализован в полном объёме по причине громоздкости и схематичности описания, но он оказал определяющее влияние на исследования, связанные с ИИ в 1970-х годах.

▍ Picat

Одним из представителей современного логического программирования является язык Picat, в своём роде «наследник» Плэнера.

Picat сочетает в себе логическое программирование, императивное программирование и удовлетворение ограничений.

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

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

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

+---+
|   |
| G |
|O  |
+---+

Одним из решений будет перемещение в (1, 0), а затем в (1, 1).

В модуле планировщика Picat можно предложить такое решение:

import planner.
import util.

main =>
   Origin = {0, 0}
   , Goal = {2, 2}
   , Start = {Origin, Goal}
   , best_plan(Start, Plan)
   , println(Plan)
   .

При этом также надо сохранять значение текущей позиции и цели:

final({Pos, Goal}) => Pos = Goal.

И описать алгоритм действия:

action(From, To, Action, Cost) ?=>
  From = {{Fx, Fy}, Goal}
  , Dir = [{-1, 0}, {1, 0}, {0, -1}, {0, 1}] 
  , member({Dx, Dy}, Dir)                    % (a)
  , Tx = Fx + Dx
  , Ty = Fy + Dy
  , member(Tx, 0..10)                        % (b)
  , member(Ty, 0..10)                        % (b)
  , To = {{Tx, Ty}, Goal}
  , Action = {move, To[1]}
  , Cost = 1
  .

И это всё. Вот результат работы программы:

> picat planner1.pi

[{move,{1,0}},{move,{2,0}},{move,{2,1}},{move,{2,2}}]

Автор затем описывает, как добавить множественные цели и алгоритм минимизации пути.

Это пример использования современного языка, предок которого изначально были изобретён для задач робототехники, а сейчас может применяться для различных задач ИИ, в том числе для управления ботами в играх, где он называется Goal Oriented Action Planning (GOAP). Например, как боты на КДПВ. Подробнее про GOAP можно почитать в этой подборке статей.

Источник

А вот ещё один пример использования планировщика из официальной документации, часть программы для решения «проблемы фермеров»:

import planner.

go =>
    S0 = [s,s,s,s],
    best_plan(S0,Plan),
    writeln(Plan).

final([n,n,n,n]) => true.

action([F,F,G,C],S1,Action,ActionCost) ?=>
    Action = farmer_wolf,
    ActionCost = 1,        
    opposite(F,F1),
    S1 = [F1,F1,G,C],
    not unsafe(S1).

...

В данном примере табулирование, дополненное методами разделения сроков, раннего завершения и поиска с ограничением ресурсов показано как лучшая альтернатива планированию, чем ASP и PDDL-планировщики на основе SAT.

В целом, планировщики (planning) — это очень интересная область исследования. Существуют различные решатели (solvers), которые соревнуются друг с другом (по производительности, качеству решений и т. д.) в международном конкурсе (International Planning Competition).

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

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

▍ Проблема со специализированными языками, но Плэнер тут ни при чём

В последнее время некоторые специалисты говорят об определённых проблемах при использовании специализированных языков (Domain-Specific Language, DSL). Вплоть до того, что те не оправдывают возложенных на них надежд. Конечно, эта проблема не касается конкретно Плэнера или Picat, но можно описать ситуацию в двух словах, чтобы получить общее представление о проблеме.

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

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

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

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

Конечно, эти рассуждения не относятся ко всем специализированным языкам в принципе. Но сама идея «no code программирования» силами низкоквалифицированных сотрудников вызывает большие сомнения. И никакие новые языки программирования, насколько лёгкими и удобным они бы ни были, не решают эту проблему в полной мере. Мы упоминаем об этом здесь только потому, что разработка на чём-то вроде Плэнера тоже может показаться лёгкой, по сравнению с другими языками, но на самом деле никто не заменит работу настоящего квалифицированного программиста.

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