энциклопедия находится в процессе разработки...

Энциклопедия интеллектуального планирования

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я

A

A search — "алгоритм А" — информированный (эвристический) алгоритм поиска. См. подробнее алгоритмы поиска.

A* searchалгоритм поиска A, для которого гарантирована невозможность переоценки (оценка стоимости пути меньше либо равна реальной стоимости пути). См. подробнее алгоритмы поиска.

AAAI (American Association for Artificial Intelligence) — Американская ассоциация искусственного интеллекта — некоммерческая организация, занимающаяся проблемами ИИ в США. Основана в 1979 г. Сайт www.aaai.org.

ABSTRIPS — планировщик, разработанный в 1974 году Эрлом Сасердоти (Erl Sacerdoti). Основная идея заключается в использовании иерархии абстрактных пространств поиска для того, чтобы на каждом уровне абстракции отделять действительно важную информацию от несущественных в данный момент деталей, и тем самым отсекать нерелевантные ветви поиска уже на верхних уровнях абстракции. В этом планировщике абстрагировались предусловия действий, т.е. сначала рассматривалось небольшое число предусловий, и строился план, затем количество предусловий увеличивали. Подробнее см. описание ABSTRIPS в разделе "История планирования".

ABTWEAKPOP-планировщик, разработанный в 1990 году Квианом Янгом (Qiang Yang) и Джошем Тененбергом (Josh Tenenberg). Авторы перенесли идею иерархии абстрактных пространств из ABSTRIPS в планировщик с частичным упорядочением действий (а именно, TWEAK).

action — см. действие.

action schema или action schemata — см. схема действия.

ADL (Action Definition Language) — язык планирования предложенный в 1989 году Эдвином Педнолтом. Язык основан на STRIPS-формализме описания доменов и задач планирования, но является более строго формализованным и, кроме того, были расширены выразительные способности языка. Главное отличие от STRIPS-языка заключается в том, что отрицается допущение о замкнутости мира. Подробнее см. описание ADL в материалах о языках для задачи планирования.

AIPS (International Conference on AI Planning & Scheduling) — международная конференция по интеллектуальному планированию и составлению расписаний. Проводилась с 1992 по 2002 годы, упразднена с появлением ICAPS.

ALPINE/PRODIGY —

AltAlt (абревиатура от "A Little of This a Little of That") — универсальный (domain-independent) планировщик, представляющий собой объединение методологии планировщика Graphplan и эвристического планирования в пространстве состояний. AltAlt использует структуру графа планирования (из Graphplan) для построения эффективных эвристик, которые затем используются планировщиком в пространстве состояний для выбора перспективных ветвей поиска. Первая версия планировщика участвовала в соревнованиях IPC-2000. Авторы: Subbarao Kambhampati, XuanLong Nguyen (Lisp версия) и Romeo Sanchez Nigenda (C++ версия).

application domain — см. domain.

axiom — см. аксиома предметной области.


B

backjamping — см. откат.

backmarking — см. откат.

backtracking — см. откат.

BDD (binary decision diagram) — см. бинарные диаграммы решения.

best-first search — класс информированных поисковых алгоритмов, осуществляющих оценку перспективности ветвей поиска и рассматривающих в первую очередь наиболее перспективные направления. См. подробнее алгоритмы поиска.

bidirectional search — двунаправленный поиск. См. подробнее алгоритмы поиска.

blackbox — планировщик, вобравший в себя идеи Graphplan и SATPLAN. Сначала строится граф планирования, на основании которого задача планирования переформулируется в булевскую задачу выполнимости (boolean satisfiability problem). После этого решается именно задача выполнимости и затем из решения извлекается план (как в SATPLAN). Реализован гибкий подход к решению задачи выполнимости — в процессе поиска решения поочередно могут пробоваться разные методы. Это дает возможность планировщику решать широкий спектр задач.

block world — см. мир кубиков.

boolean satisfiability problem (или просто SAT) — задача проверки выполнимости формулы логики высказываний. Часто решение сводится к отысканию интерпретации, в которой формула истинна (можно также говорить об отыскании модели для формулы), т.е. ищется такое присваивание истинностных значений (true или false) атомарным формулам в исходной формуле, при которых эта исходная формула станет истинной. В общем случае задача является NP-полной. Если формула является конъюнкцией клауз Хорна, то задача решается за полиномиальное время.
См. также алгоритмы решения задачи выполнимости:
- DP-алгоритм — только проверка выполнимости,
- DPLL-алгоритм, GSAT, WalkSAT, tableau, Satz, Rel-Sat — осуществляют также поиск интерпретации.

breadth-first search — поиск в ширину. См. подробнее алгоритмы поиска.

Buridan — корректный и полный стохастический планировщик, в основе которого лежит поиск в пространстве планов. Стохастический характер планирования обусловлен тем, что задача планирования ставится несколько иначе, чем в классическом планировании. Во-первых, эффекты действий зависят не только от состояния модели мира, но и от случайных событий. Тот или иной эффект может проявиться с определенной долей вероятности, а не безусловно (как в классическом планировании). Во-вторых, высказываниям, описывающим начальное состояние, также приписана вероятность их появления. Планировщик ищет план, который достигает цель с вероятностью не меньше заданной. Авторами системы Buridan являются Nicholas Kushmerick, Steve Hanks и Daniel Weld. Разработана система в 1995 году.


C

case-based planning — см. планирование на основе прецедентов.

case-based reasoning — см. рассуждения на основе прецедентов.

causal link — см. причинная связь.

CBJ (сокр. от conflict-directed backjumping) — см. откат.

CBP (сокр. от case-based planning) — см. планирование на основе прецедентов.

CBR (сокр. от case-based reasoning)— см. рассуждения на основе прецедентов.

CHEF — планировщик, опирающийся на методологию рассуждений по прецедентам. Разработан в 1990 году Кристианом Хэмондом (Kristian J. Hammond). Прикладная область — кулинария — приготовление блюд, обладающих определенными свойствами.
В качестве прецедента сохраняется не только информация об успешных эпизодах планирования, но и информация о сбоях (fault), возникших в процессе получения плана. Последнее позволяет предсказывать и избегать возникновения подобных ситуаций в будущем. При хранении планы индексируются по целям, достижению которых они служат, и по проблемам, которых следует избегать, если пользоваться данным решением.
Система учится сразу трем аспектам:
- новым планам,
- свойствам, по которым можно предсказать возникновение проблем,
- методам ремонта, который должен быть выполнен в случае возникновения таких проблем в новых обстоятельствах.
Как и большинство других CBR-систем, CHEF строит новые планы на основе хранящихся в памяти прецедентов. Прежде чем искать подходящий план и модифицировать его, CHEF исследует цели и предсказывает сбои, которые могут возникнуть из-за взаимовлияния планов, которые будут использованы для достижения этих целей. Это предсказание выполняется на основе проблем, которые планировщик встречал в прошлом. Когда сбой предсказан, CHEF добавляет цель "избежать этого сбоя" в изначальный список целей. CHEF умеет не только предсказывать сбои и избегать их, но и ремонтировать планы в случае, если сбой все-таки возникнет.
CHEF состоит из 6 модулей.
- Anticipator — предсказывает проблемы, с которыми возможно придется столкнуться при планировании. Предсказание основано на информации о сбоях, возникавших при взаимовлиянии целей, подобных текущим.
- Retriever — ищет в памяти план, который соответствует как можно большему количеству текущих целей и в то же время, пытаясь избежать проблем, предсказанных на предыдущем шаге.
- Modifier — изменяет найденный план для достижения тех целей, которые еще не достигаются найденным планом; опирается на библиотеку правил модификации.
- Repairer — вызывается, если новый план не срабатывает. Он строит причинное объяснение сбоя, ремонтирует план и передает рабочий план в модуль Storer для индексации и сохранения. Опирается на словарь сбоев — специальный индекс общих методов ремонта планов.
- Assigner — использует причинное объяснение, построенное модулем Repairer, для выявления характеристик, которые будут в дальнейшем использованы для предсказания сбоев.
- Storer — сохраняет план в памяти. Выполняет индексацию по целям, которые достигаются планом, и проблемам, которых он избегает.

classical planning см. классическое планирование.

clause см. клауза.

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

closed-world assumption — см. допущение о замкнутости мира.

CNF-formula (Conjunctive Normal Form Formula) — формула в конъюнктивной нормальной форме.

competing needs — конкурирующие требования — в планировщике Graphplan, ситуация когда, одно из предусловий одного действия является взаимно исключающим по отношению к какому-либо предусловию другого действия, находящегося на одном уровне с первым.

complete algorithm — алгоритм, обладающий полнотой. В случае алгоритма планирования это значит, что, если план существует, то он будет найден этим алгоритмом.

conditional effect — см. условный эффект.

conflict-directed backjumping (CBJ) — см. откат.

constraint posting — см. наложение ограничений.


D

DDB (dependency-directed backtracking) — способ осуществления откатов, при котором откат выполняется в точку, в которой был сделан последний выбор, ответственный за то, что поисковый алгоритм зашел в тупик (и возникла необходимость отката).

decision problem — задача принятия решения.

declobbering (устранение угрозы) — в планировщике TWEAK (и его последователях) так обозначается способ устранения негативного влияния шага, представляющего собой угрозу причинной связи в плане. Выделяют три способа устранения угрозы: demotion (понижение), promotion (повышение) и separation (разделение).

demotion (понижение) — в планировщике TWEAK (и его последователях) термином demotion обозначается способ устранения угрозы (declobbering) путем перемещения представляющего угрозу шага (clobber) до шага, обеспечивающего выполнение находящегося под угрозой предусловия.

depth-first search — поиск в глубину. См. подробнее алгоритмы поиска.

depth-limited search — ограниченный поиск в глубину (или поиск в глубину с барьером). См. подробнее алгоритмы поиска.

DerSNLP — DERivational SNLP— планировщик, опирающийся на методологию рассуждений по прецедентам. Разработан в 1994 году; авторы Laurie H. Ihrig и Subbarao Kambhampati.
В качестве прецедентов хранятся не конечные планы, а способы их получения (трассы вывода решений). Предварительное решение получается при помощи механизма "переигрывания" (replay). Затем это решение адаптируется при помощи алгоритма SNLP. Т.е. переигрывание дает нам новое начальное состояние (предположительно находящееся ближе к решению) и формирует некоторый фрагмент плана, а затем работает обычный планировщик. Трасса вывода всегда переигрывается до конца (хотя некоторые инструкции трассы могут пропускаться, в силу того, что не выполнимы в новых условиях).

Deviser

DGP (Distributed Graphplan) — алгоритм планирования, основанный на подходе планировщика Graphplan и осуществляющий планирование распределенно (при помощи двух агентов). Для этого задача планирования (цель и множество действий) разбивается на два фрагмента. В данной реализации декомпозиция выполняется вручную. Планировщик IG-DGP делает это автоматически. Авторы обоих алгоритмов (как DGP, так и IG-DGP) Марк Ивен (Mark Iwen) и Эмол Мали (Amol Dattatraya Mali).

domain — 1) в узком смысле см. домен планирования. 2) в широком смысле см. предметная область.

DP algorithm (Davis-Putnam algorithm или Pavis-Putnam procedure) — корректный и полный алгоритм проверки выполнимости формулы логики высказываний, находящейся в конъюнктивной нормальной форме (КНФ) (чаще говорят о выполнимости множества клауз). Алгоритм опирается на три правила "упрощения" конъюнктивной формулы: правило единичных клауз (unit rule), правило чистых литералов (pure literal rule) и правило резолюции.
- Правило единичных клауз. Если клауза является единичной (unit clause), т.е. дизъюнкция состоит из одного литерала, то такую клаузу можно сделать выполнимой только путем присваивания атомарной формуле (литерала) такого истинностного значения, которое делает литерал истинным.
- Правило чистых литералов. Если атомарная формула встречается только с одной полярностью (либо только положительные литералы, либо только отрицательные), то она называется чистой (pure). Чистые литералы всегда могут быть означены таким образом, что все клаузы, их содержащие, станут истинными. Поэтому такие клаузы просто удаляются из рассмотрения.
Сам алгоритм формально можно записать следующим образом.

procedure DP(S) // здесь S — формула в КНФ, выполнимость которой проверяет алгоритм (или множество клауз)

1. // Применяем правило единичных клауз.
    Пока есть единичные клаузы в S,
        Обозначим x — литерал единичной клаузы. Для выполнимости S он должен быть истинным.
        Удаляем все клаузы, в которых есть литерал x.
        В оставшихся клаузах удаляем литералы ¬x.
        Если образуется пустая клауза, то возвращаем "формула невыполнима" и прерываем выполнение.

2. // Применяем правило чистых литералов.
    Пока в S есть атомарные формулы, имеющие только одну полярность,
        Удаляем все клаузы, в которых есть такие атомарные формулы.

3. Если клауз не осталось, то возвращаем "формула выполнима" и прерываем выполнение .

4. Выбираем одну из оставшихся атомарных формул (обозначим ее y).
5. В S добавляем все возможные резольвенты по y.
6. Удаляем из S все тривиальные клаузы (тавтологии) и все клаузы, содержащие y или ¬y.

7. Переход к п.1.

Позднее была разработана более совершенная модификация этого алгоритма (DPLL), расходующая значительно меньший объем памяти (шаг 5 в худшем случае приводит к квадратичному росту числа клауз). Часто в литературе DP-алгоритмом ошибочно называют именно DPLL-алгоритм.
Алгоритм назван в честь авторов: Мартина Дэвиса (Martin Davis) и Хилари Патнема (Hilary Putnam). Разработан в 1960 году.

DPLL algorithm (Davis-Putnam-Logemann-Loveland) — корректный и полный алгоритм проверки выполнимости формулы логики высказываний, а также поиска модели для формулы. Формула должна находиться в конъюнктивной нормальной форме (КНФ) (часто рассматривается как множество клауз). Алгоритм может также использоваться с целью отыскания модели для заданной формулы (в виде набора истинностных значений для атомарных формул, содержащихся в проверяемой формуле).
DPLL-алгоритм является модификацией DP-алгоритма, но он более экономно расходует память и, кроме того, находит модель, в которой формула выполнима. В данном алгоритме вместо резолюции по выбранной атомарной формуле (шаг 5 DP-алгоритма) было использовано правило разделения (splitting rule): атомарной формуле поочередно присваиваются значения истина и ложь и уже при этом допущении процедура вновь рекурсивно вызывается.
Формально, алгоритм выглядит следующим образом.

function DPLL(S) // здесь S — формула в КНФ, выполнимость которой проверяет алгоритм (или множество клауз)

1. // Применяем правило единичных клауз.
    Пока есть единичные клаузы в S,
        Обозначим x — литерал единичной клаузы. Для выполнимости S он должен быть истинным.
        Удаляем все клаузы, в которых есть литерал x.
        В оставшихся клаузах удаляем литералы ¬x.
        Если образуется пустая клауза, то возвращаем "формула невыполнима".

2. // Применяем правило чистых литералов.
    Пока в S есть атомарные формулы, имеющие только одну полярность,
        Удаляем все клаузы, в которых есть такие атомарные формулы.

3. Если клауз не осталось, то возвращаем "формула выполнима".

4. Выбираем одну из оставшихся атомарных формул (обозначим ее y).
5. Вызываем DPLL(S ^ y) // эквивалентно y="истина" (по правилу единичных клауз)
    Если вызов вернул "формула выполнима", то возвращаем "формула выполнима".
6. Вызываем DPLL(S ^ ¬y) // эквивалентно y="ложь" (по правилу единичных клауз)
    Если вызов вернул "формула выполнима", то возвращаем "формула выполнима".

7. Возвращаем "формула невыполнима".

Важным направлением для улучшения этого алгоритма является нахождение хорошей стратегии выбора очередного литерала для присваивания истинностного значения.
Алгоритм опубликован в 1962 году.

DPPlan — вариант планировщика Graphplan, осуществляющий поиск решения в графе путем упрощения его при помощи логических правил вывода. Авторы: M. Baioletti, S. Marcugini, A. Milani.

dynamic backtracking — см. откат.


E

EBL (сокр. от explanation-based learning) — см. обучение на основе объяснения.

ECP (European Conference on Planning) — европейская конференция по планированию. Проводилась с 1990 по 2001 годы, упразднена с появлением ICAPS.

effect — см. эффект.

environment — см. среда планирования.

establishment (утверждение) — в планировщике TWEAK (и его последователях), установление каузальной связи между рассматриваемой целью и некоторым предшествующим шагом, в котором эта цель достигается. Или, иными словами, это установление связи между целью (подцелью) и эффектом действия, которое служит достижению этой цели.

explanation-based learning — см. обучение на основе объяснения.


F

feasible planning — планирование с целью получения всего лишь осуществимого (feasible) плана (без оптимизационных и иных экстрацелевых условий). В литературе обычно противопоставляется именно планированию с оптимизацией.

FF (сокр. от FastForward) — планировщик, являющий собой развитие идей планировщика HSP (прямой поиск и эвристическая оценка расстояния до цели без учета списков удалений в действиях). В отличие от HSP функция расчета эвристических оценок этого планировщика принимает во внимание то, что однажды достигнутый факт может являться предусловием нескольких последующих действий. Для выполнения этого расчета в FF строится граф планирования (см. Graphplan). Кроме того, в отличие от HSP, использовалась другая поисковая стратегия, являющаяся комбинацией hill climbing и систематического алгоритма поиска (например, можно использовать обход в ширину). В FF использовались также дополнительные эвристики, позволявшие иногда сократить пространство поиска.
FF стал победителем IPC-2000. Планировщик разработан Йоргом Хоффманом (Jorg Hoffmann) и Бернаром Нэбелем (Bernhard Nebel).

Fikes, Richard E. — известный специалист в области искусственного интеллекта, профессор Стэнфордского университета (Stanford University). Один из соавторов системы STRIPS.

flaw — (можно переводить как дефект) — это отсутствие для некоторого предусловия P шага S гарантии в том, что во время исполнения плана предусловие P будет необходимо истинным непосредственно перед выполнением S. Обычно термин используется в POP-планировании, где конкретизируется в следующую фразу. В POP предусловие (или подцель) имеет дефект, если к нему либо не проведена каузальная связь, либо каузальная связь, проведенная к предусловию, находится под угрозой. Или, применительно к плану, план содержит дефект, если в плане имеется либо открытое условие (open condition), либо небезопасная каузальная связь (unsafe link).

fluent — см. флюента.

FOL (сокр. от First-Order Logic) — логика первого порядка или исчисление предикатов первого порядка.

FORBIN

forward search — прямой поиск в пространстве состояний, когда поиск начинается от начального состояния задачи планирования. Противопоставляется обратному поиску (backward search).

frame action — см. no-op.

frame problem — см. проблема фрейма.


G

GAM (Goal Agenda Manager) — в планировщике IPP, модуль, упорядочивающий множества подцелей.

General Problem Solver — см. Универсальный решатель задач.

goal — см. цель.

GPS (сокр. от General Problem Solver) — см. Универсальный решатель задач.

Graphplan

greedy regression-match graph

greedy search — жадный поиск. См. подробнее алгоритмы поиска.

ground formula (или ground formulae) — см. означенная формула.

GSAT (greedy SAT) — корректный, но неполный алгоритм проверки выполнимости формулы логики высказываний, а также поиска модели для формулы. Формула должна находиться в конъюнктивной нормальной форме (КНФ) (часто рассматривается как множество клауз). Алгоритм осуществляет "жадный" (greedy) локальный поиск модели.
Принцип работы алгоритма следующий. Сначала генерируется случайная интерпретация (набор истинностных значений для всех атомарных формул, входной формулы). Затем отыскивается атомарная формула, изменение истинностного значения которой приводит к максимальному увеличению числа истинных клауз во входной формуле. Значение найденной атомарной формулы изменяется на противоположное (авторы называют эту операцию переворачиванием — flip). Этот процесс продолжается, пока
- либо не будет найдена интерпретация, являющаяся моделью (или, другими словами, пока не будет найдено такое присваивание (истинностных значений атомарным формулам), при котором входная формула становится истинной);
- либо не будет достигнут наперед заданный предел максимального числа переворачиваний истинностного значения.
Если после этого модель не найдена, то снова генерируется случайная интерпретация, и процесс повторяется, пока не будет выполнено наперед заданное максимальное число попыток.
Приведем формальную запись алгоритма.

function GSAT(S, MaxFlips, MaxTries)
// Здесь S — формула в КНФ, модель для которой ищет алгоритм (или множество клауз),
// MaxFlips — максимальное число переворачиваний,
// MaxTries — максимальное число попыток.

for i := 1 to MaxTries

T := сгенерированное случайным образом
       присваивание истинностных значений атомарным формулам в S.
for j := 1 to MaxFlips

if (T является моделью для S), then return T.
p := атомарная формула такая, что изменение ее истинностного значения влечет
       максимальное увеличение числа клауз в S, которые выполнимы при условии T.
T := T с инвертированным значением p.

end-for

end-for
return "модель не найдена".

Алгоритм разработан в 1992 году Бартом Селманом (Bart Selman), Эктором Левеском (Hector Levesque) и Дэвидом Митчелом (David Mitchell).


H

HACKER — решатель задач, основанный на анализе средств и целей, наборе эвристик и запоминании ранее найденных решений. Разработан Джеральдом Сусманом (Gerald Sussman) в 1973 году. Известен, благодаря тому, что эксперименты с этой системой вскрыли проблему зависимости подцелей в составной цели. Ален Браун (Allen Brown) при работе с HACKER обнаружил пример, названный в дальнейшем аномалией Сусмана, который демонстрирует возможность зависимости подцелей и, следовательно, несостоятельность допущения линейности.

HAP (Highly Adjustable Planner) или HAPRC — домено-независимый планировщик, осуществляющий поиск в пространстве состояний. Использует методы машинного обучения. Планировщик разработали Вракас (Vrakas, D.), Цоумакас (Tsoumakas, G.), Бассилиадэс (Bassiliades, N.), Влагавас (Vlahavas, I.) в 2003 году.

HAPNN — модификация планировщика HAP с другим алгоритмом машинного обучения. Авторский коллектив не изменился.

hierarchical planning — см. иерархическое планирование.

Hierarchical Task Network — см. иерархическое планирование.

hill climbing — неполный, информированный алгоритм поиска, выбирающий каждый следующий узел таким образом, чтобы он был ближе к решению, чем текущий. Если такого узла нет (то есть, достигнут локальный максимум или "плато"), то алгоритм останавливается. Иногда в литературе этот алгоритм путают с жадным алгоритмом поиска (greedy search). Но жадный алгоритм ищет, не просто какой-либо шаг, приближающий к решению, а "наилучший" шаг, максимально приближающий к решению. Кроме того, жадный алгоритм является полным; он не останавливается в точке максимума.

Horn clause — см. клауза Хорна.

HSP (Heuristic Search Planner) — планировщик, выполняющий прямой поиск (forward search) в пространстве состояний (то есть, от начального состояния к конечному) и использующий независимую от домена эвристику для оценки расстояния до цели, причем знания, на которые опирается эвристика, автоматически извлекаются из описания задачи планирования.
Планировщик работал в рамках STRIPS-доменов, предварительно выполнялась инстанциация всех схем действий. Для расчета эвристической функции выполнялись следующие шаги. Сначала задача упрощалась путем отбрасывания всех списков удалений в действиях. Таким образом, добавление очередного действия в последовательность действий могло приводить лишь к увеличению числа литералов в описании состояния. Затем, начиная от начального состояния, строились все возможные цепочки действий. При этом для каждого литерала в состоянии рассчитывалась оценка минимального количества шагов в плане, необходимых для достижения этого литерала. Алгоритм построения цепочек действий останавливался, когда ни одна из оценок не изменялась при добавлении очередного действия. Эвристическая функция, определяющая стоимость каждого из возможных в данном состоянии шагов, рассчитывалась как сумма таких оценок для каждой из целей задачи планирования. Поиск плана осуществляется каким-либо информированным алгоритмом поиска (на IPC-98 авторы использовали hill climbing), использующим эту эвристическую функцию.
Планировщик разработан Блей Бонет (Blai Bonet) и Эктором Геффнером (Hector Geffner) в 1998 году; реализован на языке Си. На IPC-98 бы лучшим по количеству решенных задач.

HSPr — регрессионная версия планировщика HSP; то есть использовался не прямой, а обратный поиск в пространстве состояний.

HSTS

HTN (сокр. от Hierarchical Task Network) — см. иерархическое планирование.


I

ICAPS (International Conference on Automated Planning and Scheduling) — международная конференция по автоматическому планированию и составлению расписаний. Проводится с 2003 года и являет собой замену конференциям AIPS и ECP.

IDA* — поисковый алгоритм, основанный на поиске с постепенным заглублением и использующий идею алгоритма A*. См. подробнее алгоритмы поиска.

IG-DGP ("Interaction Graphs"-based DGP) — алгоритм DGP, реализующий декомпозицию цели и множества действий автоматически.

in-place graph expansion

incomplete plan — см. частичный план.

inconsistent effects — см. interference.

inconsistent support — в планировщике Graphpan, ситуация, когда на одном уровне высказываний (литералов) находятся два литерала, все способы достижения одного из которых исключают возможность достижения другого. То есть каждое из действий (включая no-op), добавляющее первый литерал взаимно исключает каждое из действий, добавляющее второй литерал.

initial state — см. начальное состояние.

interference — интерференция/вмешательство — в планировщике Graphplan, ситуация, когда одно действие удаляет предусловие или элемент списка добавления другого действия, находящегося на том же уровне. Иногда, в литературе интерференцию разделяют на:
- несовместимость эффектов (inconsistent effects) - когда результат одного действия отрицает результат другого;
- и собственно, интерференцию (interference) - когда один из результатов первого действия является отрицанием какого-либо предусловия второго действия.

interleaving — см. чередование шагов.

Interplan — неполный линейный планировщик на основе анализа средств и целей с дополнительной эвристической функциональностью, направленной на решение аномалии Сусмана посредством переупорядочивания подцелей в процессе планирования. Разработан Остином Тейтом (Austin Tate) в 1974 году.

IPC (International Planning Competition) — международные соревнования планировщиков. Проводятся с 1998 года.

IPP — развитие планировщика Graphplan, разработанное командой Яны Коелер (Jana Koehler) в 1997-99 годах. IPP поддерживает условные эффекты и кванторы всеобщности в эффектах, а также более сложные (по сравнению с Graphplan) предусловия. Кроме этого, реализованы методы RIFO и GAM. IPP — лучший планировщик для ADL-доменов на IPC-98. С 1998 года поддерживает метрическое планирование и планирование с ресурсами. Планировщик реализован на языке Си.

iterative deeping search — поиск с постепенным заглублением. См. подробнее алгоритмы поиска.

IxTeT


J

.


K

Kambhampati, Subbarao — известный исследователь проблемы интеллектуального планирования, профессор Аризонского университета (Arizona State University).


L

least commitment — см. слабое связывание.

level off — в планировщике Graphplan, ситуация, когда построение очередного уровня графа планирования не приводит ни к появлению новых литералов или действий, ни к исчезновению каких-либо отношений взаимного исключения. На русский может переводиться как "стабилизация" или "выравнивание".

linearity assumption — см. допущение линейности.

linearization — см. линеаризация.

literal — см. литерал.

LPG


M

MACROP (сокр. от MACRo OPerators) — развитие (надстройка) системы STRIPS, целью которого, было повышение производительности планировщика за счет машинного обучения. Система запоминала обобщенные цепочки действий (которые были названы макрооператорами), для повторного использования их при решении новых задач планирования.

maintenance action — см. no-op.

Manhattan distance — способ оценки расстояния между двумя точками; в отличие от евклидовского расстояния, которое равно длине отрезка, соединяющего точки, манхеттенское расстояние рассчитывается как сумма длин проекций этого отрезка на оси координат. Например, в случае двумерного пространства, если у нас есть точки A(xa, ya) и B(xb, yb), то манхеттенское расстояние между этими точками вычисляется по формуле |xa - xb| + |ya - yb|.

MAXPLAN

MDP (Markov Decision Process) —

MEA (сокр. от means-ends analysis) — см. анализ средств и целей.

means-ends analysis — см. анализ средств и целей.

memoization — в планировщике Graphplan, кэширование групп недостижимых целей (чтобы избежать их анализа при дальнейшем поиске).

modal truth criterion — см. критерий модальной истинности.

model checking

MOLGEN


N

NAF — см. negation as failure.

negation as failure — отрицание как неуспех — интерпретация логического отрицания, согласно которой отрицание формулы истинно, если не может быть доказана истинность формулы. Противопоставляется классическому пониманию отрицания, согласно которому отрицание формулы истинно, если формула ложна; а если формула ни истинна, ни ложна, то отрицание формулы также считается неопределенным. Термин "отрицание как неуспех" тесно связан с допущением о замкнутости мира — все утверждения, которые явно не объявлены как истинные, считаются ложными.

Nilsson, Nils J. — крупный специалист в области искусственного интеллекта, заслуженный профессор Стэнфордского университета (Stanford University). Один из соавторов системы STRIPS. Автор ряда книг по искусственному интеллекту.

no-op — в планировщике Graphplan, фиктивное действие позволяющее литералу сохраняться истинным при переходе от какого-либо уровня высказываний к следующему (по времени) уровню. Фактически они отражают возможность появления литерала в следующем временном уровне. Это возможно, если на этом временном отрезке не будет выполнено никаких действий. Для литерала X (если рассматривать его в STRIPS-нотации) действие no-op будет иметь в качестве предусловия X, в качестве списка добавления X, а список удаления будет пустым. В литературе действия no-op ("ничего-не-делать") именуют также "сохраняющими действиями" (persistence actions или maintenance actions или frame actions).

NOAH (сокр. от Nets Of Action Hierarchies) — первый иерархический планировщик и первый планировщик, допускающий частичное упорядочивание действий. Разработан в 1975 году Эрлом Сасердоти (Erl Sacerdoti) в рамках проекта "система компьютерной консультации" (Computer Based Consultant Project).

non-linear planner — см. нелинейный планировщик.

nonholonomic planning — планирование движений в пространстве (motion planning), когда модель предметной области содержит дифференциальные ограничения (ограничения, содержащие производную). Термин был предложен Ломондом (Laumond) для описания задач планирования движений для колесных роботов.

NONLINиерархический планировщик с возможностью частичного упорядочивания действий, разработанный Остином Тейтом (Austin Tate) в 1996 году. Являет собой развитие идей планировщика NOAH.


O

O-PLAN

open conditionв POP-планировании, предусловие (подцель), к которому еще не проведена каузальная связь.


P

PABLO — планировщик, использующий абстрагирование (путем ослабления цели и предусловий действий). Разработан Кристенсеном (Christensen) в 1990.

Paragraph — вероятностный планировщик, основанный на методологии Graphplan. Авторы: Iain Little и S. Thiebaux.

PARIS

partial plan — см. частичный план.

partial-order plan — см. частично упорядоченный план.

partial-order planning — см. планирование, допускающее частичное упорядочивание действий.

PDDL (сокр. от Planning Domain Definition Language) — язык описания доменов и задач планирования. Появился в 1998 году в ответ на потребность разработки единого языка для всех видов планировщиков для проведения соревнований IPC. Со временем язык модифицируется; сейчас (2005 год) существуют следующие версий языка (PDDL v1.2, PDDL v2.1, PDDL v2.2, PPDDL v1.0, PDDL v3.0). Подробнее см. описание PDDL в материалах о языках для задачи планирования. См. также язык планирования.

persistence action — см. no-op.

PL-PLAN — библиотека планировщиков на языке Java. Реализовано несколько поисковых технологий для классической среды: Graphplan и шесть вариантов POP-планировщиков. Авторы: Philippe Fournier-Viger и Ludovic Lebel.

plan — см. план.

plan modification operations — см. операции модификации плана.

plan-space search — см. поиск в пространстве планов.

PLANEX (сокр. от PLAN EXecutor) — модуль исполнения планов, генерируемых системой STRIPS.

planning — см. планирование.

planning domain — см. домен планирования.

planning environment — см. среда планирования.

planning graph — см. граф планирования.

planning language — см. язык планирования.

planning problem — см. задача планирования.

planning under uncertainty — планирование в неопределенности — планирование в недетерминированных средах (например, при наличии контрагента или неизвестной динамики) или планирование в частично наблюдаемых средах.

PMO (сокр. от plan modification operation) — см. операции модификации плана.

POCL planning (сокр. от partial-order causal-link planning) — см. планирование, допускающее частичное упорядочивание действий.

POMDP (Partially Observable Markov Decision Process) —

POP (сокр. от 1) partial-order planning или 2) partial-order plan) — 1) см. планирование, допускающее частичное упорядочивание действий. 2) см. частично упорядоченный план.

postcondition — иногда этим термином в литературе обозначают эффект действия.

precondition — см. предусловие.

precondition flaw — см. flaw.

problem solving

PRODIGY

progression

promotion (повышение) — в планировщике TWEAK (и его последователях) термином promotion обозначается способ устранения угрозы (declobbering) путем перемещения представляющего угрозу шага (clobber) после шага, предусловие которого находится под угрозой.

proposition — в логике, высказывание.

propositional fluent — см. флюента.


Q

QA3 (Question Answering system, version 3) — вопросно-ответная система, в круг задач которой входил поиск ответа на вопросы вида "Существует ли последовательность действий такая, что ...". Система работала на основе доказательства теорем методом резолюции в логике предикатов первого порядка. В QA3 предложена формализация задачи планирования при помощи логики предикатов (с возможностью задания начального состояния), допускалось формулировать аксиомы предметной области и условные эффекты. Система разработана в 1969 году Корделом Грином (Cordell Green). Подробнее см. обзор по QA3.

qualification problem — см. проблема ограничительных условий.


R

ramification problem — см. проблема косвенных эффектов.

refinement planning

regression или goal regression

regression-match graph — см. greedy regression-match graph.

regression focussing

replay

RePOP

resolution (или resolution rule) — см. резолюция.

RIFO (Removing Irrelevant Facts and Operators) — в планировщике IPP, стратегия, позволяющия сократить размер графа планирования за счет удаления нерелевантных фактов и действий.


S

SAPA

SAT — см. boolean satisfiability problem.

SATPLANпервый планировщик, основанный на SAT-парадигме (в противовес дедуктивному и поисковому подходам). SAT-планировщик предполагает сведение задачи планирования к задаче выполнимости. Такой подход показал себя довольно эффективным на задачах, которые традиционно считаются "трудными" для поискового подхода. Кроме того, он обладает рядом дополнительных полезных свойств. Например, легко можно накладывать ограничения на промежуточные состояния (наличие определенного факта в промежуточном состоянии) или задать ограничение на используемые действия (план должен содержать определенные действия). В SATPLAN задача планирования сначала конвертируется в такую SAT-задачу, что всякая модель полученной формулы соответствует плану. Затем может быть применен какой-либо алгоритм решения задачи выполнимости для нахождения модели. В SATPLAN были опробованы классический DPLL-алгоритм и жадный эвристический алгоритм GSAT, а также ряд их модификаций. После того, как модель найдена, из нее извлекается конечный план. SATPLAN разработан Генри Каутцем (Henry Kautz) и Бартом Селманом (Bart Selman) в 1992 году.

scheduling — см. составление расписаний.

search algorithms — см. алгоритмы поиска.

separation (разделение) — в планировщике TWEAK термином separation обозначается способ устранения угрозы (declobbering) путем такого означивания параметров предикатов, описывающих предусловие и потенциально опасный эффект, что предикаты (из предусловия и опасного эффекта) становятся различными. Примечание: в TWEAK в действительности оперируют понятием высказывания (proposition), а не предикатами. Но понятие высказывания из TWEAK не соотносится с понятием высказывания, которое мы знаем из математики. Поэтому мы говорим здесь о предикатах, дабы избежать путаницы.

SGP (Sensory Graphplan) —

SHOP (Simple Hierarchical Ordered Planner) —

SIPE (System for Interactive Planning and Execution) —

situation

situational calculus — см. ситуационное исчисление.

situational fluent — см. флюента.

SNLP

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

SPA

SRI или SRI International — независимый исследовательский институт в Калифорнии (США). До 1970 года был подразделением Стэнфордского университета. Отсюда аббревиатура SRI — Stanford Research Institute.

STAN

state — см. состояние модели мира.

state-space search

STRIPS (STanford Research Institute Problem Solver) — система, которая традиционно считается первым планировщиком. В STRIPS были сформулированы многие базовые принципы современного планирования. В частности, был разработан формализм описания задач планирования (на базе которого строятся современные языки планирования), было предложено использовать допущение о замкнутости мира и STRIPS-допущение. Система была создана в 1979 году; авторы — Ричард Файкс и Нильс Нильсон. Подробнее см. обзор по STRIPS.

STRIPS-assumption (STRIPS-допущение) — постулирует, что все формулы, которые содержатся в состоянии, в котором действие применяется, но не упоминающиеся в эффекте действия, будут содержаться и в результирующем состоянии действия. STRIPS-допущение решает проблему фрейма.

STRIPS-operator

STRIPS-формализм (или STRIPS-язык) —

Sussman anomaly — см. аномалия Сусмана.


T

tableau

task

task formalism

task reduction planning (или просто task reduction)— см. иерархическое планирование.

Tate, Austin — известный исследователь в области интеллектуального планирования и представления действий, профессор Эдинбургского университета (University of Edinburgh, UK). Тейт является автором систем Interplan и NONLIN, принимал участие в разработке системы O-Plan.

TF (сокр. от task formalism) — см. task formalism.

TGP

TIM

threat — см. угроза.

TLPlan

TOP (сокр. от total-order planning) — см. total-order planning.

total-order planning

triangle table — структура для хранения макрооператора в системе MACROP.

TWEAK


U

UBTREE — реализация memoization в планировщике IPP.

UCPOP — полный и корректный POP-планировщик, поддерживающий подмножество ADL, а именно, условные эффекты, кванторы всеобщности в предусловиях, эффектах и целях. Планировщик полноценно реализует слабое связывание: частичный порядок действий и отложенное означивание переменных. Авторы: J. Scott Penberthy и Daniel S. Weld.

uniform-cost search — равностоимостный поиск. См. подробнее алгоритмы поиска.

UNPOP — ... Язык реализации: Common Lisp. Автор: Drew McDermott.

unsafe link — в POP-планировании, каузальная связь, находящаяся под угрозой (threat).


V

Veloso, Manuela M.

VHPOP (Versatile Heuristic Partial Order Planner) —


W

WalkSAT (или WSAT) —

WARPLAN

wave front

Weld, Daniel S.

wff (сокр. от well-formed formula) — правильно (корректно) построенная формула.

white knight

world model — см. модель мира.

WSAT — см. WalkSAT.


X

.


Y

Yale shooting problem
Примечание. Yale — сокращение от Yale University — Йельский университет (США).


Z

.


А

аксиома предметной области — элемент описания домена предметной области, отражающий различного рода взаимосвязи между свойствами объектов. Функционально аксиомы служат для упрощения описаний схем действий и позволяют разделять непосредственный эффект действия и косвенный эффект, обусловленный тем, что действие изменяет некоторые свойства объектов, от которых зависят другие свойства (возможно других объектов). Именно эту зависимость и отражает аксиома. Следует отметить, что аксиомы носят не только декларативный, но и процедурный характер. Т.е. они не только отражают взаимосвязь между свойствами объектов, но и используются для корректировки результата применения действия, чтобы этот результат не противоречил задекларированным аксиомам.
Если в описании домена присутствуют аксиомы, то действие порождает не состояние, а некоторый "промежуточный результат", который становится состоянием лишь после применения аксиом. Назовем этот промежуточный результат "черновым состоянием" (draft state). Черновое состояние может состоять в противоречии с аксиомами. Тогда необходимо применить аксиомы, чтобы получить корректное состояние. Аксиомы действуют как правила вывода, но они не добавляют новые факты, а лишь вносят поправки в черновое состояние (по крайней мере, когда факты представлены литералами). Применение происходит следующим образом. Пусть в результате выполнения какого-либо действия мы получаем черновое состояние S. После этого просматриваются условия применимости всех аксиом, и если какая-то аксиома оказывается применимой, то она применяется для модификации S (в корректном домене порядок применения аксиом не должен играть роли). Процесс продолжается до тех пор, пока все аксиомы не окажутся неприменимыми. В момент, когда ни одна из аксиом не может быть применена, S становится действительным состоянием (не черновым), и к нему можно применять следующее действие. Применение аксиом происходит после выполнения каждого действия.

алгоритмы поиска — алгоритмы, осуществляющие поиск определенного элемента (или элементов) в каком-либо пространстве связанных элементов (графе). Можно выделить два класса поисковых алгоритмов: комбинаторные (неинформированные) и эвристические.
Комбинаторные алгоритмы осуществляют "слепой" перебор элементов пространства поиска, осуществляя переход от одного элемента к другому по связи между ними. Хорошо известны и исследованы следующие 6 видов неинформированного поиска:
- поиск в ширину (breadth-first search);
- равностоимостный поиск (uniform-cost search);
- поиск в глубину (depth-first search);
- ограниченный поиск в глубину (depth-limited search);
- постепенное заглубление (iterative deeping search);
- двунаправленный поиск (bidirectional search).
Равностоимостный поиск. Поиск в ширину всегда находит "ближайшее" решение (минимальное количество дуг в решении). Но это не всегда оптимальное решение (дуги могут иметь разную стоимость). В отличие от поиска в ширину при равностоимостном поиске в первую очередь рассматриваются пути, имеющие пока наименьшую стоимость.
Постепенное заглубление. Проблема ограниченного поиска в глубину заключается в удачном выборе барьера. Постепенное заглубление — это ограниченный поиск в глубину с постепенным увеличением глубины (при каждом увеличении глубины поиск начинается с начала). Это приводит к повторному рассмотрению ряда узлов, но минимизируется расход памяти (как при поиске в глубину) и ищется наиболее короткое решение (как при поиске в ширину).
Эвристические алгоритмы перебирают элементы на основе некоторого принципа, определяющего наилучшее направление поиска, т.е. используются знания о предметной области. Как правило, это делается путем присвоения узлам (или дугам) пространства поиска некоторых оценок стоимости (оценок перспективности направления). Традиционно используется следующее соглашение: чем меньше оценка, тем перспективнее направление. Тогда суть эвристического алгоритма будет сводиться к рассмотрению в первую очередь лучших (с наименьшей оценкой) направлений поиска (best-first search) или к поиску только в направлении улучшения оценки (например, hill climbing). Известно несколько способов определения оценок для узлов. Например, алгоритм жадного поиска (greedy search) оценивает стоимость достижения цели (расстояние до цели). Чем ближе цель, тем перспективнее направление поиска. Алгоритм A (A algorithm) кроме перспективности направления поиска учитывает еще и "стоимость" пройденного пути. Для каждого направления поиска вычисляется специальная оценочная функция, имеющая форму f(n) = g(n) + h(n), где n — узел, представляющий одно из возможных направлений поиска, g — функция оценки стоимости пройденного пути (от начального состояния до n), h — функция оценки стоимости пути от вершины n до какой-либо целевой вершины. Таким образом, алгоритм А сочетает в себе преимущества равностоимостного поиска и жадного алгоритма. Если оценка h всегда меньше реальной минимальной стоимости пути от n к целевой вершине (т.е. переоценка невозможна), то алгоритм называют A* (иногда алгоритм называют в честь авторов — алгоритм Харта, Нильсона и Рафаэля). Для экономии памяти иногда пользуются объединением идей алгоритмов постепенного заглубления и A*. Такой алгоритм называют IDA*. В основе лежит методология постепенного заглубления, но вместо барьера по глубине используется барьер по стоимости.

анализ средств и целей

аномалия Сусмана


Б

базовая формула — синоним означенной формулы (ground formula).

бинарные диаграммы решения — .


В

.


Г

граф планирования — в планировщике Graphplan, специальная структура (граф), описывающая задачу планирования таким образом, что многие ограничения, неявно присутствующие в постановке задачи, становятся явными, что позволяет сократить пространство поиска.


Д

действие — механизм перевода модели предметной области из одного состояния в другое, а также описание этого механизма. Если обозначить S — множество всех возможных состояний модели предметной области, то всякое действие A будет являться одноместной (как правило, частично определенной) функцией, отображающей некоторое множество Si (SiÍS) состояний, в которых применение действия допустимо, во множество So (SoÍS) состояний, получающихся в результате применения действия. Действие является полностью конкретизированным в отличие от схемы действия.
В классическом планировании действия описываются при помощи конструкции, содержащей три составляющие: имя действия, его предусловие и эффект. Предусловие описывает условия применимости действия в данном состоянии модели мира (предусловие определяет множество Si). Эффект описывает изменения, которые необходимо внести в исходное состояние для получения результирующего состояния (эффект совместно с Si определяет So). Обычно предусловие и эффект определяются формулами исчисления предикатов первого порядка (если состояния модели мира также определяются формулами). Тогда проверка предусловия сводится к проверке истинности формулы предусловия в данном состоянии (все формулы, описывающие состояние считаются истинными), а применение действия сводится к добавлению и удалению формул из состояния.
В неклассическом планировании действие может иметь более сложное описание и содержать, например, схему декомпозиции, вероятностные коэффициенты для эффектов, условные эффекты, манипуляции с числовыми величинами (ресурсами), темпоральные параметры и т.д.

дизъюнкт — в логике, дизъюнкция литералов.
В статьях по искусственному интеллекту вместо "дизъюнкт" часто используются термин клауза, который с формальной точки зрения является тем же самым (дизъюнкция литералов). Однако в математических статьях "правильнее" писать именно "дизъюнкт".

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

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

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


Е

.


Ж

.


З

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


И

иерархическое планирование — .


К

каузальная связь — см. причинная связь.

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

клауза — см. дизъюнкт.
Происходит от англоязычного clause. Встречаются переводы: клоза, предложение.

клауза Хорна — в логике, формула вида
(p & q & ... & t) —> u,
где p,q,..,t,u - атомарные формулы. Посылка импликации может содержать сколько угодно таких атомарных формул, объединенных операцией конъюнкции (в том числе и ноль формул).
Эта формула может быть приведена к эквивалентной ей дизъюнктивной форме (отсюда название — клауза).
(¬p) v (¬q) v ... v (¬t) v u.
Клауза Хорна названа в честь американского математика Альфреда Хорна.

КНФ — см. конъюнктивная нормальная форма.

конъюнктивная нормальная форма — в логике, формула находится в конъюнктивной нормальной форме, если она имеет вид конъюнкции клауз.

критерий модальной истинности


Л

линеаризация — построение какого-либо полного (total) порядка на множестве действий в частично упорядоченном плане. Таких "полных порядков" для одного и того же частично упорядоченного плана может быть несколько.

литерал — в логике, атомарная формула или ее отрицание.


М

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

метод резолюции — метод автоматического доказательства теорем от противного (proof by contradiction или refutation theorem-proving technique). В основе метода лежит правило резолюции. Суть метода состоит в следующем:

1. Порождается конъюнкция из всех формул в базе знаний (фактов, аксиом) и отрицания доказываемой формулы (гипотезы (conjecture)).

2. Получившаяся формула приводится к конъюнктивной нормальной форме (рассматриваемой как множество клауз).

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

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

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

См. также "Об автоматическом доказательстве теорем" в материалах сайта.

мир блоков — см. мир кубиков.

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

модель — в логике, такая интерпретация множества формул, в которой все формулы данного множества истинны.

модель мира


Н

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

начальное состояние — в задаче планирования, (формальное) описание модели мира (состояния) в момент времени, непосредственно предшествующий моменту начала выполнения плана.

незавершенный план — см. частичный план.

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


О

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

означенная формула (ground formula) — формула логики предикатов (первого порядка), не содержащая переменных (т.е. состоящая только из предикатных символов, функциональных символов, константных символов, символов связок, скобок и запятых; переменные, а следовательно и кванторы, недопустимы). Фактически это высказывание.
Не следует путать означенную формулу с замкнутой (не содержащей свободных вхождений переменных).
В литературе встречается также как термин базовая формула.

операции модификации плана

откат — технический прием, осуществляемый алгоритмами поиска для возврата к ранее игнорировавшимся ветвям поиска в случае, если анализ текущей ветви поиска зашел в тупик. В частности, откат используется алгоритмом поиска в глубину (deep-first search).
Существует два класса стратегий отката. Простые или хронологические откаты осуществляют пошаговый возврат согласно пути поиска. Более интеллектуальные стратегии, такие как backmarking, backjumping, conflict-directed backjumping (CBJ) и dynamin backtracing, пытаются отыскать узел пути поиска, в котором было принято неверное решение.


П

план — последовательность действий, ведущая к намеченной цели.

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

планирование, допускающее частичное упорядочивание действий (или POP-планирование) —

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

планирование по прецедентам — см. планирование на основе прецедентов.

планирование с классическими допущениями — см. классическое планирование.

поиск в пространстве планов

правило резолюции — см. резолюция.

предметная область — множество всех предметов (объектов, сущностей), свойства которых и отношения между которыми рассматриваются в научной теории.

предусловие (действия) —

причинная связь (или каузальная связь) — в POP-планировщиках элемент плана, определяющий, каким действием достигается некоторая определенная цель (подцель). Можно сказать, что причинная связь связывает эффект одного действия с предусловием другого.

проблема косвенных эффектов (ramification problem) — проблема формального описания всех последствий выполнения действия (всех эффектов). Детальное описание предметной области может быть очень громоздким.
Подробнее см. проблемы ситуационного исчисления.

проблема ограничительных условий или проблема спецификации (qualification problem) — суть проблемы состоит в том, что очень трудно перечислить все условия, которые могут препятствовать выполнению действия.
Подробнее см. проблемы ситуационного исчисления.

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

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


Р

рассуждения на основе прецедентов — методология обучения по примерам, согласно которой знания о способах решения проблем приобретаются в процессе функционирования системы. Основная идея методологии рассуждений по прецедентам состоит в том, что подобные проблемы имеют подобные решения. Системы, основанные на этой методологии, решают проблемы путем адаптации и применения методов решения проблем, с которыми ранее система уже имела дело. Опыт накапливается в специальных структурах, называемых прецедентами. Фактически, прецедент — это пара <постановка задачи, метод решения>. Прецеденты хранятся в специальном хранилище, называемом библиотекой прецедентов. Методология рассуждений на основе прецедентов (в общем случае) реализуется в циклической процедуре, состоящей из четырех процессов:
- поиска подходящего прецедента (retrieve),
- применение метода решения (из прецедента) к новой постановке задачи (reuse),
- проверка полученного решения и, если необходимо, корректировка (адаптация) решения (revise),
- сохранение полученного решения (как прецедента) для последующего использования (retain).
Часто эти процессы называются 4Re-процессами. Весь цикл рассуждений по прецедентам можно представить следующей диаграммой.

CBR-цикл

резольвента — результат применения правила резолюции — клауза.

резолюция (или правило резолюции) — в математической логике и теории автоматического доказательства теорем, правило вывода, которое из двух клауз, содержащих взаимодополняющие литералы (например, Q и ¬Q) , порождает новую клаузу, состоящую из литералов исходных клауз, за исключением взаимодополняющих. Клауза, порожденная правилом резолюции, называется резольвентой (resolvent). Правило используется для автоматической проверки выполнимости формулы (см. DP algorithm) и доказательства теорем (см. метод резолюции).


С

ситуационное исчисление — формальный язык, который может быть использован для описания модели мира и выполнения рассуждений о воздействиях на мир. Разработан Джоном Маккарти (John McCarthy) в 1963 году. Подробнее см. ситуационное исчисление. См. также язык планирования.

слабое связывание

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

состояние модели мира

среда планирования — условия, при которых происходит процесс планирования. Среда определяется рядом свойств исполнителя и мира, а именно:
- Способен ли исполнитель полностью наблюдать мир (возможно ли заранее полностью построить модель мира).
- Статичен ли мир (может ли мир меняться независимо от действий исполнителя).
- Полностью ли детерминированы действия исполнителя (нет ли стохастических параметров).
- Дискретны или длительны действия во времени (имеют ли действия длительность).
- Допустимо ли параллельное исполнение действий.
Таким образом, можно говорить, что среда планирования определяется кортежем:
<World observability, World static character, Action determinancy, Action durability, Action parallelism>.
Особо выделяют среду классического планирования.

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


Т

.


У

угроза (threat) — в POP-планировании, возникновение следующей ситуации. Обозначим "s-P—>w" причинную связь между шагами s и w (предусловие P шага w достигается эффектом шага s). Тогда шаг v представляет собой угрозу для данной причинной связи, если v:
- отличен от s и w,
- имеет эффектом P или ¬P,
- может находиться между шагами s и w.

Универсальный решатель задач — интеллектуальная система поиска решений, разработанная А. Ньюэлом, Дж. Шоу и Г. Саймоном в 1957-69 годах. Первая система для решения задач, в которой общие методы решения были отделены от знаний, определяющих конкретную задачу (отсюда "универсальный"). В процессе разработки этой системы была создана методология поиска, именуемая "анализ средств и целей". Именно эта методология легла в основу поисковой процедуры первого планировщика (STRIPS). Подробнее см. обзор по Универсальному решателю задач.

условный эффект


Ф

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


Х

.


Ц

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


Ч

частично упорядоченный план

частичный план — план, построение которого еще не завершено. Фактически, это частично-определенный или частично-построенный план. Термин преимущественно используется в контексте планирования в пространстве планов (частично-определенных планов).

чередование шагов


Ш

.


Щ

.


Э

эффект (действия) — те изменения модели предметной области, которые происходят в случае применения действия.


Ю

.


Я

язык планирования — этим термином называются формальные языки описания задач планирования и предметных областей (или доменов), в рамках которых решаются эти задачи. К наиболее известным языкам планирования относятся ситуационное исчисление, STRIPS-формализм, ADL, PDDL.


Трофимов И.В.

октябрь 2005 г