Скачать 1.15 Mb.
|
Алгоритм STRIPSАлгоритм STRIPS приведен в табл.1
Табл.1. Алгоритм STRIPS На вход алгоритма STRIPS подаётся множество правил R, начальное состояние s0, цель 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) Начальное состояние s0 и цель 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). Применяет найденную последовательность к состоянию s0. Получается ситуация, изображённая на рис.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 стр.
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. |
![]() | Конспект лекций по дисциплине "Программное обеспечение интеллектуальных систем". Для магистров специальности 5А521902 Целью данного курса является приобретение знаний по разработки и реализации основных элементов систем искусственного интеллекта | ![]() | Лабораторная работа №1 по дисциплине “Системы искусственного интелекта Исчисление предикатов первого порядка является теоретической основной множества формализмов методов искусственного интеллекта. Задачи... |
![]() | «шаг за шагом» создание искусственного интеллекта гашева Светлана Интеллект рассматривают как прикладную область исследований, связанных с имитацией отдельных функций интеллекта человека [6]. Распознавание... | ![]() | Учебно-методический комплекс по дисциплине “основы искусственного интеллекта” ... |
![]() | «Основы искусственного интеллекта» Рабочая учебная программа по дисциплине «Основы искусственного интеллекта» для ооп «050100 Физика и информатика по циклу б в. 13... | ![]() | Рабочая программа дисциплины «Системы искусственного интеллекта» Рабочая программа основана на требованиях Федерального государственного стандарта высшего профессионального образования по направлению... |
![]() | Учебно-методический комплекс по дисциплине “основы искусственного интеллекта” для специальности ... | ![]() | Учебно-методический комплекс по дисциплине “основы искусственного интеллекта” для специальности ... |
![]() | В. К. Финн к структурной когнитологии: феноменология сознания с точки зрения искусственного интеллекта Ки и искусственного интеллекта – полигона экспериментальной проверки научных средств имитации рациональности и продуктивного мышления.... | ![]() | 1. интеллектуальные системы Системы искусственного интеллекта, решающие задачи по обработке знаний и при этом проявляющие черты, сходные с чертами естественного... |