A. A. Zuenko, S. Yu. Yakovlev, A. S. Shemyakin, Yu. A. Oleynik Application of constraint programming technology for planning action in emergency situations
A. A. Zuenko, S. Yu. Yakovlev, A. S. Shemyakin, Yu. A. Oleynik Application of constraint programming technology for planning action in emergency situations


The authors developed a technology of AI planning, focused on the study of poorly formalized subject domains, knowledge about which is quantitative and qualitative. The technology provides support for the domain model open for operational modifications, allowing the inclusion / exclusion of restrictions, quality criteria, as well as setting the initial and target states using undetermined parameters. The problem of AI planning is proposed to be set and solved in the framework of an objectoriented extension of the programming technology, which places increased demands on the efficiency of processing qualitative constraints. It is proposed to present the qualitative constraints in the form of specialized matrix-like structures, and their processing should be carried out using the author's methods of non-numerical constraint satisfaction. The proposed approach allows structuring semantically closely coupled quantitative and qualitative constraints, simplifying their maintenance, as well as speeding up their automatic generation and processing. As an example of an applied task, the paper considers a simplified version of the task of planning actions for the localization of a territorial spill of petroleum products.


AI planning, poorly formalized subject domain, constraint satisfaction problem, constraint programming, object-oriented representation, emergency situation.

PP. 26-37.

DOI 10.14357/20718632190103


1. Russel, S., and P. Norvig. 2010. Artificial Intelligence: A Modern Approach. 3rd edition. Prentice Hall. 1132 p.
2. Smith, D. E., J. Frank, and Ari K. Jónsson. 2000. Bridging the Gap Between Planning and Scheduling. Knowledge Engineering Review. 15(1):47-83.
3. Blum, A. and M. Furst. 1997. Fast planning through planning graph analysis. Artificial Intelligence 90:281-300.
4. Rintanen, J. 2009. Planning and SAT. In A. Biere, H. van Maaren, M. Heule and T. Walsh, Eds. Handbook of Satisfiability. IOS Press. 483-504.
5. Steger-Jensen, K., H.-H. Hvolby, P. Nielsen, and I. Nielsen, 2011. Advanced planning and scheduling technology. Production Planning and Control. Vol. 22. 8:800–808.
6. Bit-Monnot, A. 2018. A Constraint-Based Encoding for Domain-Independent Temporal Planning. Proceedings of 24th International Conference “Principles and Practice of Constraint Programming”. Lille. 30-46. doi: 10.1007/978-3-319-98334-9.
7. Margaux, N., C. Artigues, and P. Lopez. 2017. Cumulative scheduling with variable task profiles and concave piecewise linear processing rate functions. Constraints. Vol. 22. 4:530-547.
8. Kreter, S., J. Rieck, and J. Zimmermann. 2016. Models and solution procedures for the resource-constrained project scheduling problem with general temporal constraints and calendars. European Journal of Operational Research. 251(2):387-403.
9. Letort, A., M. Carlsson, and N. Beldiceanu. 2015. Synchronized sweep algorithms for scalable scheduling constraints. Constraints. Vol. 20, 2:183-234. doi: 10.1007/s10601-014-9172-8.
10. Prikaz MChS Rossii No 621. 2004. Ob utverzhdenii Pravil razrabotki i soglasovaniya planov po preduprezhdeniyu i likvidacii razlivov nefti i nefteproduktov na territorii RF. [Order no. 621 of EMERCOM of Russia. About approval of the Rules for the development and coordination of plans for the prevention and elimination of spills of oil and oil products in the territory of the Russian Federation].
11. Yakovlev, S. Yu., A.A. Ry`zhenko, and N.V. Isakevich. 2010. Razrabotka planov po preduprezhdeniyu i likvidacii razlivov nefteproduktov dlya territorial`ny`x ob``ektov [Development of plans for the prevention and elimination of oil spills for territorial objects]. Modelirovanie i analiz bezopasnosti i riska v slozhny`x sistemax: Trudy` Mezhdunarodnoj nauchnoj shkoly` MABR-2010[Modeling and analysis of safety and risk in complex systems: Proceedings of the International Scientific School MASR-2010]. Saint-Peterburg. 447-452.
12. Zuenko A. 2019. Matrix-like Structures for Representation and Processing of Constraints Over Finite Domains. Advances in Intelligent Systems and Computing. Springer Nature Switzerland AG. Vol. 875:428-438. doi:10.1007/978-3-030-01821-4_45.
13. Zuenko A.A., Lomov P.A., and Oleynik A.G. 2017. Primenenie metodov rasprostraneniya ogranicheniy dlya uskoreniya obrabotki zaprosov k ontologiyam [Applying constraint propagation methods to speed up the processing of ontology requests]. Trudy SPIIRAN [SPIIRAS Proceedings]. 1(50):112-136. doi: 10.15622/sp.50.5
14. Zuenko, Alexander, and Y. Oleynik. 2019. Programming of Algorithms of Matrix-Represented Constraints Satisfaction by Means of Choco Library. Advances in Intelligent Systems and Computing. Springer Nature Switzerland AG. Vol. 875:1-10. doi: 10.1007/978-3-030-01821-4_46.

2023 / 02
2023 / 01
2022 / 04
2022 / 03

© ФИЦ ИУ РАН 2008-2018. Создание сайта "РосИнтернет технологии".