Развитие логического подхода к решению задач интеллектуального планирования: аналитический обзор
Ключевые слова:
интеллектуальное планирование, автоматическое планирование, выполнимость конъюнктивной нормальной формы, задача удовлетворения ограничений, распространение ограничений, программирование в ограничениях, табличные ограничения
Аннотация
В настоящей статье приводится аналитический обзор применения методов на основе логического подхода для решения классических задач интеллектуального планирования, в которых предполагается детерминированность действий исполнителей, а также не анализируется продолжительность действий и не учитываются количественные ресурсы. В отличие от теории расписаний, где основное внимание почти всегда уделяется решению задач конкретного типа, в интеллектуальном планировании разрабатываются общие методы решения широкого спектра задач с применением их декларативного описания. Возможно, именно поэтому такую популярность при решении задач интеллектуального планирования получил логический подход, предполагающий декларативное представление знаний и унифицированные механизмы рассуждений. В представленной работе предлагается авторская классификация систем интеллектуального планирования на основе логического подхода. К наиболее исследуемым в последнее время системам планирования на основе развития данного подхода относятся системы с применением технологии программирования в ограничениях. В последнее время возрос интерес к процедурам вывода на табличных ограничениях. Помимо обычных таблиц, к табличным ограничениям относятся сжатые таблицы, smart таблицы и т. п. Табличные ограничения все чаще используются в задачах интеллектуального планирования: для эффективного решения задач высокой размерности в табличные ограничения транслируют различного рода графы, с помощью которых кодируются переходы из состояния в состояние и/или от одного действия к другому. Поэтому значительная часть представленного аналитического обзора посвящена применению табличных ограничений в задачах интеллектуального планирования. Кроме того, рассматриваются такие широко известные методы, как сведение задач планирования к поиску доказательства теорем, трансляция графа планирования в задачи выполнимости конъюнктивной нормальной формы и задачи удовлетворения ограничений.
Скачивания
Данные скачивания пока не доступны.
Литература
1. Allen J. (1983) Maintaining Knowledge about Temporal Intervals. Communications of the ACM. 26(11). P. 832–843.
2. Allen J., Kautz H. and Pelavin R. (1991) Reasoning About Plans. Morgan Kaufmann.
3. Apt K. R. (2003) Principles of Constraint Programming. Cambridge University Press.
4. Artificial intelligence. Systems and Models. [Electronic resource] Available from: URL
5. Bartak R. (2011) A novel constraint model for parallel planning. Proceedings of the International FLAIRS Conference.
6. Bartak R. (2011) On constraint models for parallel planning: The novel transition scheme. Proceedings of the 11th Scandinavian Conference on Artificial Intelligence. P. 50–59.
7. Bartak R. and Toropila D. (2008) Reformulating constraint models for classical planning. Proceedings of the International FLAIRS Conference. P. 525–530.
8. Bartak R. and Toropila D. (2009) Enhancing constraint models for planning problems. Proceedings of the International FLAIRS Conference.
9. Bartak R. and Toropila D. (2009) Revisiting constraint models for planning problems. International Symposium on Methodologies for Intelligent Systems. P. 582–591.
10. Ben Zhou, Kyle Richardson, Qiang Ning, Tushar Khot, Ashish Sabharwal and Dan Roth (2021) Temporal Reasoning on Implicit Events from Distant Supervision. Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. P. 1361–1371.
11. Blum A. L. and Furst M. L. (1997) Fast planning through planning graph analysis. Artificial intelligence. 90 (1-2). P. 281–300.
12. Blum A. and Furst M. (1995) Fast planning through planning graph analysis. Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI – 95). Montreal, Canada. P. 1636–1642.
13. Chengyu Wang, Xiaofeng He and Aoying Zhou (2018) Event phase oriented news summarization. World Wide Web. 21(4). P. 1069–1092.
14. Christer Backstrom and Bernhard Nebel (1995) Complexity Results for SAS+ Planning Computational Computational Intelligence. Vol. 11, 4.
15. Dechter R. (2003) Constraint Processing. Morgan Kaufmann.
16. Do M. B. and Kambhampati S. (2001) Planning as constraint satisfaction: Solving the planning-graph by compiling it into CSP. Artificial Intelligence. 132 (2). P. 151–182.
17. Dong T. (2012) Recognizing Variable Environment – The Theory of Cognitive Prism. Studies in Computational Intelligence. Springer-Verlag, Berlin Heidelberg. Vol. 388.
18. Rossi F., Van Beek P. and Walsh T. (ed) (2006) Handbook of Constraint Programming. Elsevier.
19. Fikes R. E. and Nilsson N. (1971) J. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence. 2. P. 189–208.
20. Gent I. P., Jefferson C. and Miguel I. (2006) MINION: a fast, scalable, constraint solver. Proceedings of the 17th European Conference on Artificial Intelligence. P. 98–102.
21. Ghallab M. and Laruelle H. (1994) Representation and control in IxTeT, a temporal planner. Proceedings of AIPS-94. P. 61–67.
22. Ghallab M., Nau D. S. and Traverso P. (2004) Automated Planning: Theory and Practice. Elsevier.
23. Ghanbari, Namazi, Newton and Sattar (2017) Encoding Domain Transitions for Constraint-Based Planning. Journal of Artificial Intelligence Research. 58. P. 905–966.
24. Green C. (1969) Application of Theorem Proving to Problem Solving. IJCAI’69. P. 219–240.
25. Green C. C. (1969) 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, 4.
26. Gregory P., Long D. and Fox M. (2010) Constraint based planning with composable substate graphs. Proceedings of the 19th European conference on Artificial Intelligence. P. 453–458.
27. Helmert M. (2006) The fast downward planning system. Journal of Artificial Intelligence Research. 26. P. 191–246.
28. Helmert M. (2009) Concisenite-domain representations for PDDL planning tasks. Artificial Intelligence. 173 (5-6). P. 503–535.
29. Jefferson C. and Nightingale P. (2013) Extending simple tabular reduction with short supports. Proceedings of IJCAI-13.
30. Joslin D. and Pollack M. (1996) Is “Early Commitment” in Plan Generation Ever a Good Idea? Proceedings of the Thirteenth National Conference on Artificial Intelligence. Mcnlo Park, Calif. P. 1188–1193.
31. Judge M. and Long D. (2011) Heuristically guided constraint satisfaction for planning. Proceedings of the 29th Workshop of the UK Planning and Scheduling Special Interest Group.
32. Kautz H. and Selman B. (1992) Planning as satisfiability. Proceedings of ECAI. P. 359–363.
33. Kautz H. and Selman B. (1996) Pushing the Envelope: Planning Propositional Logic and Stochastic Search. Proceedings of the Thirteenth National Conference on Artificial Intelligence. Menlo Park, Calif. P. 1194–1201.
34. Kumar V. (1992) Algorithms for constraint-satisfaction problems: A survey. AI Magazine. 13(1). P. 32–44.
35. Lecoutre C. (2011). STR2: Optimized simple table reduction for table constraints. Constraints. 16 (4). P. 341–371.
36. Lopez A. and Bacchus F. (2003) Generalizing graphplan by formulating planning as a CSP. Proceedings of IJCAI-03. P. 954–960.
37. McCarthy J. and Hayes P. J. (1969) Some Philosophical Problems from the Standpoint of Artificial Intelligence. Machine Intelligence. American Elsevier, New York. 4. P. 463–502.
38. McDermott D., Ghallab M., Howe A., Knoblock C., Ram A., Veloso M., Weld D. and Wilkins D. (1998) PDDL-the planning domain definition language. Tech. rep. Yale University.
39. Nadel B. Some Applications of the Constraint-Satisfaction Problem. Tech. rep № CSC90-008, Computer Science Dept., Wayne State Univ.
40. Osipov G. S. (2011) Metody iskusstvennogo intellekta [Artificial intelligence methods]. Moscow : Fizmatlit. (in Russian).
41. R`egin Jean-Charles (1996) Generalized arc-consistency for global cardinality constraint. Proceedings of AAAI-96. P. 209–215.
42. Raphael B. (1971) The Frame Problem in Problem Solving Systems. Artificial Intelligence and Heuristic Programming. Edinburgh, Scotland: Edinburgh Univ. Press. P. 159–169.
43. Renz J., Nebel B. and Aiello M. (2007) Qualitative Spatial Reasoning using Constraint Calculi. Handbook of Spatial Logics. Springer.
44. Rujun Han, I-Hung Hsu, Mu Yang, Aram Galstyan, Ralph Weischedel and Nanyun Peng. (2019) Deep structured neural network for event temporal relation extraction. Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), Hong Kong, China. Association for Computational Linguistics.
45. Russel S. and Norvig P. (2010) Artificial Intelligence: A Modern Approach. 3rd ed. Prentice Hall. 1132.
46. Theoretical foundations of planning [Electronic resource] Available from: URL
47. Van Beek P. and Chen X. (1999) CPlan: A constraint programming approach to planning. Proceedings of AAAI-99/IAAI-99. P. 585–590.
48. Vidal V. and Geffner H. (2006) Branching and pruning: An optimal temporal POCL planner based on constraint programmming. Artificial Intelligence. 170 (3). P. 298–335.
49. Zuenko A. A. (2020) Kompaktnoye predstavleniye ogranicheniy na osnove novoy interpretatsii ponyatiya «kortezh mnogomestnogo otnosheniya». [Compact Representation of Constraints Based on a New Interpretation of the Notion of a Multiplace Relation Tuple]. Design ontology. Vol. 10, 38. P. 503–515. DOI
50. Zuenko A. A. (2022) Integratsiya kontseptual’nogo modelirovaniya i programmirovaniya v ogranicheniyakh dlya sinteza skhem tekhnologi-cheskikh protsessov [Integrating Conceptual Modeling and Constraint Programming for Flowchart Synthesis]. Information technologies and computing systems. (3). P. 95–107. (in Russian).
51. Zuenko A. A. (2022) Metod mashinnogo obucheniya dlya vyyavleniya zamknutykh mnozhestv obshchikh priznakov ob”yektov s primeneniyem tekhnologii programmirovaniya v ogranicheniyakh. [Machine learning method for identifying closed sets of common features of objects using constraint programming technology]. Automation and telemechanics. (12). P. 156–168. (in Russian).
52. Zuenko A. A., Fridman O. V. and Zuenko O. N. (2022) Paradigma programmirovaniya v ogranicheniyakh pri reshenii zadach sostavleniya raspisaniy: analiticheskiy obzor. [Constraint Programming Paradigm in Solving Scheduling Problems: An Analytical Review]. Bulletin of VSU, series: System analysis and information technologies. (4). P. 156–179. (in Russian).
53. Zuenko Alexander and Zuenko Olga (2023) Frequent Pattern Discovery as Table Constraint Satisfaction Problem. Lecture notes in networks and systems. Springer International Publishing. 566. P. 118–130.
54. Zuenko Alexander (2023) Associative classification based on the table constraint satisfaction. Springer International Publishing (in the press).
2. Allen J., Kautz H. and Pelavin R. (1991) Reasoning About Plans. Morgan Kaufmann.
3. Apt K. R. (2003) Principles of Constraint Programming. Cambridge University Press.
4. Artificial intelligence. Systems and Models. [Electronic resource] Available from: URL
5. Bartak R. (2011) A novel constraint model for parallel planning. Proceedings of the International FLAIRS Conference.
6. Bartak R. (2011) On constraint models for parallel planning: The novel transition scheme. Proceedings of the 11th Scandinavian Conference on Artificial Intelligence. P. 50–59.
7. Bartak R. and Toropila D. (2008) Reformulating constraint models for classical planning. Proceedings of the International FLAIRS Conference. P. 525–530.
8. Bartak R. and Toropila D. (2009) Enhancing constraint models for planning problems. Proceedings of the International FLAIRS Conference.
9. Bartak R. and Toropila D. (2009) Revisiting constraint models for planning problems. International Symposium on Methodologies for Intelligent Systems. P. 582–591.
10. Ben Zhou, Kyle Richardson, Qiang Ning, Tushar Khot, Ashish Sabharwal and Dan Roth (2021) Temporal Reasoning on Implicit Events from Distant Supervision. Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. P. 1361–1371.
11. Blum A. L. and Furst M. L. (1997) Fast planning through planning graph analysis. Artificial intelligence. 90 (1-2). P. 281–300.
12. Blum A. and Furst M. (1995) Fast planning through planning graph analysis. Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI – 95). Montreal, Canada. P. 1636–1642.
13. Chengyu Wang, Xiaofeng He and Aoying Zhou (2018) Event phase oriented news summarization. World Wide Web. 21(4). P. 1069–1092.
14. Christer Backstrom and Bernhard Nebel (1995) Complexity Results for SAS+ Planning Computational Computational Intelligence. Vol. 11, 4.
15. Dechter R. (2003) Constraint Processing. Morgan Kaufmann.
16. Do M. B. and Kambhampati S. (2001) Planning as constraint satisfaction: Solving the planning-graph by compiling it into CSP. Artificial Intelligence. 132 (2). P. 151–182.
17. Dong T. (2012) Recognizing Variable Environment – The Theory of Cognitive Prism. Studies in Computational Intelligence. Springer-Verlag, Berlin Heidelberg. Vol. 388.
18. Rossi F., Van Beek P. and Walsh T. (ed) (2006) Handbook of Constraint Programming. Elsevier.
19. Fikes R. E. and Nilsson N. (1971) J. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence. 2. P. 189–208.
20. Gent I. P., Jefferson C. and Miguel I. (2006) MINION: a fast, scalable, constraint solver. Proceedings of the 17th European Conference on Artificial Intelligence. P. 98–102.
21. Ghallab M. and Laruelle H. (1994) Representation and control in IxTeT, a temporal planner. Proceedings of AIPS-94. P. 61–67.
22. Ghallab M., Nau D. S. and Traverso P. (2004) Automated Planning: Theory and Practice. Elsevier.
23. Ghanbari, Namazi, Newton and Sattar (2017) Encoding Domain Transitions for Constraint-Based Planning. Journal of Artificial Intelligence Research. 58. P. 905–966.
24. Green C. (1969) Application of Theorem Proving to Problem Solving. IJCAI’69. P. 219–240.
25. Green C. C. (1969) 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, 4.
26. Gregory P., Long D. and Fox M. (2010) Constraint based planning with composable substate graphs. Proceedings of the 19th European conference on Artificial Intelligence. P. 453–458.
27. Helmert M. (2006) The fast downward planning system. Journal of Artificial Intelligence Research. 26. P. 191–246.
28. Helmert M. (2009) Concisenite-domain representations for PDDL planning tasks. Artificial Intelligence. 173 (5-6). P. 503–535.
29. Jefferson C. and Nightingale P. (2013) Extending simple tabular reduction with short supports. Proceedings of IJCAI-13.
30. Joslin D. and Pollack M. (1996) Is “Early Commitment” in Plan Generation Ever a Good Idea? Proceedings of the Thirteenth National Conference on Artificial Intelligence. Mcnlo Park, Calif. P. 1188–1193.
31. Judge M. and Long D. (2011) Heuristically guided constraint satisfaction for planning. Proceedings of the 29th Workshop of the UK Planning and Scheduling Special Interest Group.
32. Kautz H. and Selman B. (1992) Planning as satisfiability. Proceedings of ECAI. P. 359–363.
33. Kautz H. and Selman B. (1996) Pushing the Envelope: Planning Propositional Logic and Stochastic Search. Proceedings of the Thirteenth National Conference on Artificial Intelligence. Menlo Park, Calif. P. 1194–1201.
34. Kumar V. (1992) Algorithms for constraint-satisfaction problems: A survey. AI Magazine. 13(1). P. 32–44.
35. Lecoutre C. (2011). STR2: Optimized simple table reduction for table constraints. Constraints. 16 (4). P. 341–371.
36. Lopez A. and Bacchus F. (2003) Generalizing graphplan by formulating planning as a CSP. Proceedings of IJCAI-03. P. 954–960.
37. McCarthy J. and Hayes P. J. (1969) Some Philosophical Problems from the Standpoint of Artificial Intelligence. Machine Intelligence. American Elsevier, New York. 4. P. 463–502.
38. McDermott D., Ghallab M., Howe A., Knoblock C., Ram A., Veloso M., Weld D. and Wilkins D. (1998) PDDL-the planning domain definition language. Tech. rep. Yale University.
39. Nadel B. Some Applications of the Constraint-Satisfaction Problem. Tech. rep № CSC90-008, Computer Science Dept., Wayne State Univ.
40. Osipov G. S. (2011) Metody iskusstvennogo intellekta [Artificial intelligence methods]. Moscow : Fizmatlit. (in Russian).
41. R`egin Jean-Charles (1996) Generalized arc-consistency for global cardinality constraint. Proceedings of AAAI-96. P. 209–215.
42. Raphael B. (1971) The Frame Problem in Problem Solving Systems. Artificial Intelligence and Heuristic Programming. Edinburgh, Scotland: Edinburgh Univ. Press. P. 159–169.
43. Renz J., Nebel B. and Aiello M. (2007) Qualitative Spatial Reasoning using Constraint Calculi. Handbook of Spatial Logics. Springer.
44. Rujun Han, I-Hung Hsu, Mu Yang, Aram Galstyan, Ralph Weischedel and Nanyun Peng. (2019) Deep structured neural network for event temporal relation extraction. Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), Hong Kong, China. Association for Computational Linguistics.
45. Russel S. and Norvig P. (2010) Artificial Intelligence: A Modern Approach. 3rd ed. Prentice Hall. 1132.
46. Theoretical foundations of planning [Electronic resource] Available from: URL
47. Van Beek P. and Chen X. (1999) CPlan: A constraint programming approach to planning. Proceedings of AAAI-99/IAAI-99. P. 585–590.
48. Vidal V. and Geffner H. (2006) Branching and pruning: An optimal temporal POCL planner based on constraint programmming. Artificial Intelligence. 170 (3). P. 298–335.
49. Zuenko A. A. (2020) Kompaktnoye predstavleniye ogranicheniy na osnove novoy interpretatsii ponyatiya «kortezh mnogomestnogo otnosheniya». [Compact Representation of Constraints Based on a New Interpretation of the Notion of a Multiplace Relation Tuple]. Design ontology. Vol. 10, 38. P. 503–515. DOI
50. Zuenko A. A. (2022) Integratsiya kontseptual’nogo modelirovaniya i programmirovaniya v ogranicheniyakh dlya sinteza skhem tekhnologi-cheskikh protsessov [Integrating Conceptual Modeling and Constraint Programming for Flowchart Synthesis]. Information technologies and computing systems. (3). P. 95–107. (in Russian).
51. Zuenko A. A. (2022) Metod mashinnogo obucheniya dlya vyyavleniya zamknutykh mnozhestv obshchikh priznakov ob”yektov s primeneniyem tekhnologii programmirovaniya v ogranicheniyakh. [Machine learning method for identifying closed sets of common features of objects using constraint programming technology]. Automation and telemechanics. (12). P. 156–168. (in Russian).
52. Zuenko A. A., Fridman O. V. and Zuenko O. N. (2022) Paradigma programmirovaniya v ogranicheniyakh pri reshenii zadach sostavleniya raspisaniy: analiticheskiy obzor. [Constraint Programming Paradigm in Solving Scheduling Problems: An Analytical Review]. Bulletin of VSU, series: System analysis and information technologies. (4). P. 156–179. (in Russian).
53. Zuenko Alexander and Zuenko Olga (2023) Frequent Pattern Discovery as Table Constraint Satisfaction Problem. Lecture notes in networks and systems. Springer International Publishing. 566. P. 118–130.
54. Zuenko Alexander (2023) Associative classification based on the table constraint satisfaction. Springer International Publishing (in the press).
Опубликован
2024-02-05
Как цитировать
Зуенко, А. А., & Фридман, О. В. (2024). Развитие логического подхода к решению задач интеллектуального планирования: аналитический обзор. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (4), 104-127. https://doi.org/10.17308/sait/1995-5499/2023/4/104-127
Раздел
Интеллектуальные системы, анализ данных и машинное обучение
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
