Конспект лекций по дисциплине «Системы искусственного интеллекта»

Скачать 1.15 Mb.

Название	Конспект лекций по дисциплине «Системы искусственного интеллекта»
страница	10/11
Дата	05.09.2012
Размер	1.15 Mb.
Тип	Конспект

1 2 3 4 5 6 7 8 9 10 11

Алгоритм STRIPS

Алгоритм STRIPS приведен в табл.1

STRIPS

вход: R, s, G

выход: plan

1 S=S₀

2 пока G не выполнимо в s

делать

2.1. выбрать компоненту g из G

2.2. выбрать правило RR такое, что gA(R)

2.3. STRIPS (R, s, C(R))

2.4. применить R к s

2.5. добавить R в plan

3 вернуть plan

Табл.1. Алгоритм STRIPS

На вход алгоритма STRIPS подаётся множество правил R, начальное состояние s₀, цель G.

Будем полагать, что в множестве R все правила полностью конкретизированы.

Вначале в стек целей помещается главная цель G.

Если цель не является простой, т.е. содержит конъюнкцию литералов, то система STRIPS добавляет в стек в некотором порядке каждый из литералов составной цели (п.1.1). Когда верхняя цель стека является однолитеральной, система ищет действие (п.1.2), которое содержит в списке добавлений литерал, сопоставимый с этой целью. Если такое действие не применимо к текущему состоянию, тогда его предусловие помещается в стек целей, иначе действие применяется к текущему состоянию (п.1.5.) и помещается в план (plan). Если верхняя цель в стеке соответствует текущему состоянию, то она удаляется из стека. Алгоритм STRIPS завершается, когда стек пуст.

Неполнота алгоритма STRIPS.

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

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

Примечание. Впервые некорректность STRIPS'а в этом случае была вскрыта в 1973 году Аленом Брауном из Массачусетского Технологического института. Браун попытался решить задачу, рассматриваемую в этом разделе на планировщике HACKER. HACKER был создан Джеральдом Суссманом на основе планировщика STRIPS, поэтому задача получила название аномалия Суссмана (Sussman Anomaly) [58] .

Рассмотрим аномалию Суссмана

Дано:

Объекты:

3 кубика – A, B, C.

Состояние описывается предикатами:

ontable (x) – кубик x на столе,

clear (x) – над кубиком x пусто,

handempty – рука агента пуста,

holding (x) – рука агента держит кубик x,

on (x,y) – кубик x находится на кубике y.

x, y –переменные.

Правила:

R1: pickup (x) – поднять кубик со стола

C (R1): ontable (x) & clear (x) handempty

A (R1): holding (x)

D (R1): ontable (x), clear (x), handempty

R2: putdown (x) – опустить кубик на стол

C (R2): holding (x)

A (R2): ontable (x), clear (x), handempty

D (R2): holding (x)

R3: stack (x,y) – положить кубик на другой кубик

C(R3): holding (x) & clear (y)

A(R3): handempty, on (x,y), clear (x)

D(R3): holding (x), clear (y)

R4: unstack (x,y) – снять кубик с другого кубика

C(R4): handempty & on(x,y) & clear (x)

A(R4): holding (x), clear (y)

D(R4): handempty, on(x,y), clear (x)

Начальное состояние s₀ и цель G изображены на рис.1.

Таким образом, цель G= {On (A,B) & On (B,C)}.

Рис.1. Аномалия Суссмана

Поскольку цель G является составной, то STRIPS расщепляет её на отдельные компоненты – On (A,B) и On (B,C), которые помещаются в стек и удовлетворяются по очереди.

Положим, что On (A,B) наверху стека, тогда планировщик находит следующую последовательность правил для удовлетворения On (A,B): UNSTACK(C,A), PUTDOWN(C), PICKUP(A), STACK (A,B). Применяет найденную последовательность к состоянию s₀. Получается ситуация, изображённая на рис.2, в которой On (A,B) выполнима. Цель On (A,B) удаляется из стека целей.

Рис. 2. Удовлетворение первой цели

Далее, из ситуации на рис.2 , удовлетворяется следующая цель в стеке – On (B,C). В результате имеем: UNSTACK(C,A), PUTDOWN(C), PICKUP(A), STACK (A,B), UNSTACK(A,B), PUTDOWN(A), PICKUP(B), STACK (B,C). Применяем последовательность подчёркнутых правил. Получаем ситуацию на рис.3. Цель On (B,C) удовлетворена и удаляется из стека. Однако цель On(A,B), удовлетворённая на предыдущем этапе, перестаёт быть выполнимой.

Рис. 3. Удовлетворение второй цели

Поэтому, далее планировщик пытается из ситуации на рис.3 удовлетворить On (A,B). Это приводит к добавлению ещё двух правил к имеющейся последовательности.

В результате получаем план: UNSTACK(C,A), PUTDOWN(C), PICKUP(A), STACK (A,B), UNSTACK(A,B), PUTDOWN(A), PICKUP(B), STACK (B,C), PICKUP(A), STACK (A,B). Подчёркнутые правила применяются. Цель On (A,B) & On (B,C) достигается. План построен.

Однако существует другой план, содержащий меньше действий:

UNSTACK(C,A), PUTDOWN(C), PICKUP(B), STACK (B,C), PICKUP(A), STACK(A,B).

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

1. C.Клини. Математическая логика.М.:МИР,1973

2. Г.Кейслер, Ч.Ч.Чен. Теория моделей. М.: Мир, 1977.

3. Мальцев А.И. Алгебраические системы. М.: Наука, 1970

4. Fikes R.E., Nilsson N.J. STRIPS: a new approach to application of theorem proving to problem

solving. Artificial Intelligence 1971, 2.

5. Нилсон Н.Принципы искусственного интеллекта. М. МИР, 1977

6. Лорьер Ж.-Л. Системы искусственного интеллекта.М.:МИР, 1991

7. Quillian M.R. Semantic memory // Semantic Information Processing, с. 227-268, MIT Press, 1968

8. Р.Ковальски, Логика в решении проблем. М.: «НАУКА», 1990

9. В.Н.Вагин. Дедукция и обобщение в системах принятия решений.

М.: НАУКА, 1988

10. Г.С.Осипов. Приобретение знаний интеллектуальными системами. М.Наука. ФИЗМАТЛИТ, 1997.

11. Жилякова Л.Ю. Об одном классе отношений в неоднородных семантических сетях.// Изв. ТРТУ №2, Таганрог, 2000, стр. 70-73.

12. Клещёв А.С. Семантические порождающие модели. Общая точка зрения на фреймы и продукции в экспертных системах. Препринт. Владивосток: ИАПУ ДВНЦ РАН, 1986,

39 стр.

13. Donini, Francesco M., Maurizio Lenzerini, Daniele Nardi, Werner Nutt. The Complexity of Concept Language. // In Proc. of the 2^nd Int. Conf. On the Principles of Knowledge Representation and Reasoning (KR-91), 1991.
14. Dorofeyeva A. Analysis of Semantic Networks By Means of Description Logics// In Proceedings of the 1999 International Workshop on Description Logics(DL'99) Linkцping, Sweden July 30 - August 1, 1999. pp.167 – 168.
15. Шушакова А.Г. Решение задач представления и обработки знаний средствами дескриптивной логики. // Программные продукты и системы №3, 2002 – М: НТП «Фактор» – с. 14 – 19.
16.Donini F.M., Lenzerini M., Nardi D., Nutt W., Reasoning in Description Logics // In Procedings of the Second International Conference on Principles of Knowledge Representation and Reasoning. (KR-91), pp. – 151 – 162, 1991.
17.Donini F.M., Lenzerini M., Nardi D., Nutt W., The complexity of concept languages // Inform.and Comp. 134, 1997. pp: 1-58.
18. Kurtonona N., Rijke M., Expressivenes of concept espressions in first-order description logics // Artificial Intelligence, v.107, 1999.
19. F.Baader, PHanschke. A Scheme for Integrating Concrete Domains into Concept Languages.
Proc. IJCAI-91, Sydney, Australia, 1991, p 452-457.
20. Lutz C., Reasoning with Concrete Domains // Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI'99), 31 july – 6 august, 1999, Stockholm, Sweden.

17. С.Ю.Маслов. Обратный метод установления выводимости в классическом исчислении предикатов // Доклады АН СССР, - 1964, т. 159, № 1, стр. 17-20

18. Robinson J. A. Machine Oriented Logic Based on the Resolution Principle. J. ACM, 12 (January 1965), pp.23 – 41.

19. Ч.Чень, Р.Ли.Математическая логика и автоматическое доказательство теорем.

М.:»Наука», 1983

20. В.К.Финн. Интеллектуальные системы и общество. М.: УРСС, 2006

21. В.Н.Вагин, Е.Ю.Головина, А.А.Загорянская, М.В. Фомина. Достоверный и правдоподобный вывод в интеллектуальных системах. М.: Физматлит, 2004

22. Финн В.К. Правдоподобные рассуждения в ителлектуальных системах тиа ДСМ // Итоги науки и техники. М., 1991. Т. 15, стр. 54-101.

23. Аншаков О.М. Об одной интерпретации ДСМ-метода автоматического порождения гипотез. // НТИ*, №1, 1999.

24. Prakken, H. & Vreeswijk, G.A.W. (2002). Logics for defeasible argumentation. In D.M. Gabbay & F. Guenthner (Eds.), Handbook of Philosophical Logic, 2nd edition, Vol 4 (pp. 219-318). Dordrecht/Boston/London: Kluwer Academic Publishers.

25. А.Б.Беляев, М.Н.Годовников, С.А.Голубев, Е.П.Куршев, Г.С. Осипов, Л.И.Сазонова. Технология создания распределённых интеллектуальных систем. Учебное пособие. Университет г. Переславля, Переславль-Залесский, 1997.

26. Gordon A.D., Classification. London: Chapman & Hall, 1999.

27. Эфрон Б. Нетрадиционные методы многомерноо статистического аализа. М.: Финансы и статистика, 1988.

28. Назаренко Г.И., Осипов Г.С. Основы теории медицинских технологических процессов. Ч.2. Иследование медицинских технологических процессов на основе интеллектуального анализа даных. М.: Наука, Физматлит, 2006.

29. Аркадьев А.Г., Браверман Э.М. Обучение машины распознаванию образов. М.: Наука, 1964.

30. Lenz, Mario; Bartsch-Sporl, Brigitte; Burkhard, Hans-Dieter; Wess, Stefan (ed).

Case-Based Reasoning Technology: From Foundations to Applications. Lecture Notes in Artificial Intelligence. Springer, 1998.

31. Kumar V. Algorithms for constraint-satisfaction problems: A survey. // AI Magazine, 13(1):32--44, 1992. http://citeseer.nj.nec.com/kumar92algorithms.html

32. Kambhampati S., Nigenda R., Nguyen X. AltAlt: Combining the advantages of Graphplan and Heuristic State Search. // ASU Technical Report

33. Maler O., Manna Z., Pnueli A. From Timed to Hybrid systems // Real-Time: Theory in Practice, LNCS, Vol.600, с.447-484, Springer-Verlag, 1992

34. McCarthy J. Formalisation of STRIPS in situation calculus // Technical report formal reasoning Group, Dep. of Computer Science, Stanford University, 1985

35. Williams B., Nayak P. A Reactive Planner for a Model-Based Execution // Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-15). – Menlo Park, California, 1997. – c.1178-1185

36. Long D., Fox M. Efficient Implementation of the Plan Graph in STAN, V.10, p. 87-115, 1999

37. Raphael B. The frame problem in problem solving systems // Artificial Intelligence and Heuristic Programming. –1971, c.159-169. Edinburgh Univ. Press, Edinburgh, Scotland

38. McDermott, D. A Heuristic Estimator for Means-Ends Analysis in Planning // In Proceedings of the Third International Conference on AI Planning Systems. – 1996. –c.142–149. Menlo Park, Calif.: AAAI Press

39. Sussman G. A Computational Model of Skill Acquisition. // PhD thesis, MIT, Cambridge, Massachusetts, August 1973

40. Chapman D. Planning for Conjunctive Goals // Artificial Intelligence. - 1987. – №32(3). – с.333–377

41. Tate A. Generating Project Networks // Proceedings of the Fifth International Joint Conference on Artificial Intelligence. – Menlo Park, California. – 1977. – с.888–893

42. McAllester D., Rosenblit D. Systematic nonlinear planning // Proceedings of AAAI-91, Anaheim, Ca, 1991

43. Sacerdoti E.D. Planning in a hierarchy of abstraction spaces // Artificial Intelligence. – 1974. – №5. – С.115-135

44. Sacerdoti E.D. The nonlinear nature of plans // Proceedings of the Fourth International Joint Conference on Artificial Intelligence (IJCAI-75). – Tbilisi, Georgia. – 1975. – c.206-214

45. Tate A., Currie K. O-Plan: The Open planning architecture // Artificial Intelligence. – 1991. – № 52. – с.49-86

46. Wilkins D. Can AI planners solve practical problems? // Computational Intelligence. – 1990. – Том 6. – №4. – с.232-246

47. Blum A., Furst M. Fast planning through planning graph analysis // Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI – 95). – Montreal, Canada. – 1995. – с.1636 – 1642

48. Kautz H., Selman B. Planning as Satisfiability // Proceedings of the Tenth European Conference on Artificial Intelligence ({ECAI}'92)", с.359-363, 1992.

49. Koehler J., Nebel B., Hoffmann J., Dimopoulos Y. Extending Planning Graphs to an ADL Subset, ECP-97, pages 273-285, Springer LNAI 1348

50. Stoerr H. BDDPlan // http://www.ki.inf.tu-dresden.de/~stoerr/bddplan.html

51. Bonet B., Geffner H. Planning as heuristic search. // Artificial Intelligence. –2001. http://citeseer.nj.nec.com/bonet01planning.html

52. Hoffmann J., Nebel B. The FF planning system: Fast plan generation through heuristic search // Journal of Artificial Intelligence Research, 2001

53. Kambhampati S., Nigenda R., Nguyen X. AltAlt: Combining the advantages of Graphplan and Heuristic State Search. // ASU Technical Report

54. Refanidis I., Vlahavas I. "The GRT Planner: Backward Heuristic Construction in Forward State-Space Planning", Journal of Artificial Intelligence Research, 15 (2001), с. 115-161

55. Green C.C. Theorem proving by resolution as a basis for question answering systems. In Bernard Meltzer and Donald Michie, editors // Machine Intelligence, Edinburgh University Press, Edinburgh, Scotland, 1969, 4

56. Fikes R.E., Nilsson N.J. STRIPS: a new approach to application of theorem proving to problem solving // Artificial Intelligence 1971, 2

57. Newell A., Simon H. GPS, a program that simulates human thought // Computers and Thought, eds: E.A. Feigenbaum and J. Feldman, McGraw Hill, NY, 1963

58.

1 2 3 4 5 6 7 8 9 10 11

	Конспект лекций по дисциплине "Программное обеспечение интеллектуальных систем". Для магистров специальности 5А521902 Целью данного курса является приобретение знаний по разработки и реализации основных элементов систем искусственного интеллекта		Лабораторная работа №1 по дисциплине “Системы искусственного интелекта Исчисление предикатов первого порядка является теоретической основной множества формализмов методов искусственного интеллекта. Задачи...
	«шаг за шагом» создание искусственного интеллекта гашева Светлана Интеллект рассматривают как прикладную область исследований, связанных с имитацией отдельных функций интеллекта человека [6]. Распознавание...		Учебно-методический комплекс по дисциплине “основы искусственного интеллекта” ...
	«Основы искусственного интеллекта» Рабочая учебная программа по дисциплине «Основы искусственного интеллекта» для ооп «050100 Физика и информатика по циклу б в. 13...		Рабочая программа дисциплины «Системы искусственного интеллекта» Рабочая программа основана на требованиях Федерального государственного стандарта высшего профессионального образования по направлению...
	Учебно-методический комплекс по дисциплине “основы искусственного интеллекта” для специальности ...		Учебно-методический комплекс по дисциплине “основы искусственного интеллекта” для специальности ...
	В. К. Финн к структурной когнитологии: феноменология сознания с точки зрения искусственного интеллекта Ки и искусственного интеллекта – полигона экспериментальной проверки научных средств имитации рациональности и продуктивного мышления....		1. интеллектуальные системы Системы искусственного интеллекта, решающие задачи по обработке знаний и при этом проявляющие черты, сходные с чертами естественного...

Конспект лекций по дисциплине «Системы искусственного интеллекта»

Алгоритм STRIPS

Неполнота алгоритма STRIPS.

Похожие: