×

Handling fuzzy temporal constraints in a planning environment. (English) Zbl 1145.90029

Summary: An interleaved integration of the planning and scheduling process is presented with the idea of including soft temporal constraints in a partial order planner that is being used as the core module of an intelligent decision support system for the design forest fire fighting plans. These soft temporal constraints have been defined through fuzzy sets. This representation allows us a flexible representation and handling of temporal information. The scheduler model consists of a fuzzy temporal constraints network whose main goal is the consistency checking of the network associated to each partial order plan. Moreover, we present a model of estimating this consistency, and show the monitoring and rescheduling capabilities of the system. The resulting approach is able to tackle problems with ill defined knowledge, to obtain plans that are approximately consistent and to adapt the execution of plans to unexpected delays.

MSC:

90B35 Deterministic scheduling theory in operations research
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

PDDL; SAPA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Avesani, P., Perini, A., & Ricci, F. (2000). Interactive case-based planning for forest fire management. Applied Intelligence, 13(1), 41–57. · doi:10.1023/A:1008327312956
[2] Bacchus, F., & Ady, M. (2001). Planning with resources and concurrency. A forward chaining approach. In IJCAI’01.
[3] Bartõk, R., & Mecl, R. (2003). Integrating planning into production scheduling: Visopt shopfloor system. In G. Kendall, E. Burke & S. Petrovic (Eds.), Proceedings of the 1st multidisciplinary international conference on scheduling: theory and applications (MISTA) (pp. 259–278).
[4] Bienkowski, M. (1995). Demonstrating the operational feasibility of new technologies: the ARPI IFDs. IEEE Expert, 10(1), 27–33. · Zbl 05094432 · doi:10.1109/64.391960
[5] Biundo, S., & Schattenberg, B. (2001). From abstract crisis to concrete relief–a preliminary report on combining state abstraction and htn planning. In 6th European conference on planning (ECP-01).
[6] Biundo, S., Aylett, R., Beetz, M., Borrajo, D., Cesta, A., Grant, T., McCluskey, L., Milani, A., & Verfaillie, G. (2003). PLANET technological roadmap on AI planning and scheduling. Electronically available at http://www.planet-noe.org/service/Resources/Roadmap/Roadmap2.pdf .
[7] Blythe, J. (1999). Decision-theoretic planning. AI Magazine, 20(2), 37–54.
[8] Bresina, J., Dearden, R., Meuleanu, N., Ramakrishnan, A., Smith, D., & Washington, R. (2002). Planning under continuous time and resource uncertainty: a challenge for AI. In Proc. UAI.
[9] Castillo, L., Fdez-Olivares, J., & González, A. (2000). Automatic generation of control sequences for manufacturing systems based on nonlinear planning techniques. Artificial Intelligence in Engineering, 4(1), 15–30. · Zbl 05388043 · doi:10.1016/S0954-1810(99)00025-4
[10] Castillo, L., Fdez-Olivares, J., & González, A. (2001). Mixing expresiveness and efficiency in a manufacturing planner. Journal of Experimental and Theoretical Artificial Intelligence, 13, 141–162. · Zbl 1009.68647
[11] Cohen, P., Greenberg, M., Hart, D., & Howe, A. (1989). Trial by fire: understanding the design requirements for agents in complex environments. AI Magazine, 10(3), 32–48.
[12] de la Asunción, M., Castillo, L., Fdez-Olivares, J., García-Pérez, O., González, A., & Palao, F. (2003). SIADEX: assisted design of forest fire fighting plans by artificial intelligence planning techniques. http://siadex.ugr.es .
[13] de la Asunción, M., Castillo, L., Fdez-Olivares, J., García-Pérez, O., González, A., & Palao, F. (2005). SIADEX: an interactive artificial intelligence planner for decision support and training in forest fire fighting. Artificial Intelligence Communications, 18(4).
[14] Dechter, R. (2003). Constraint processing. Morgan Kaufmann. · Zbl 1057.68114
[15] Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49, 61–95. · Zbl 0737.68070 · doi:10.1016/0004-3702(91)90006-6
[16] Do, M., & Kambhampati, S. (2001). SAPA: a domain-independent heuristic metric temporal planner. In European conference on planning (pp. 109–120).
[17] Dubois, D., & Prade, H. (1978). Operations on fuzzy numbers. International Journal of Systems Science, 9, 613–626. · Zbl 0383.94045 · doi:10.1080/00207727808941724
[18] Dubois, D., Fargier, H., & Prade, H. (1993). The use of fuzzy constraints in job-shop scheduling. In Proc. of IJCAI-93/SIGMAN workshop on knowledge-based production planning, scheduling and control, Chambery, France.
[19] Dubois, D., Fargier, H., & Fortemps, P. (2003). Fuzzy scheduling: modelling flexible constraints vs. coping with incomplete knowledge. European Journal of Operational Research, 147, 231–252. · Zbl 1037.90028 · doi:10.1016/S0377-2217(02)00558-1
[20] Haslum, P., & Geffner, H. (2001). Heuristic planning with time and resources. In European conference on planning (pp. 121–132).
[21] Khatib, L., Morris, P., Morris, R., & Rossi, F. (2001). Temporal constraint reasoning with preferences. In IJCAI 2001 (pp. 322–327).
[22] Laborie, P., & Ghallab, M. (1995). Planning with sharable resource constraints. In IJCAI’95 (pp. 1643–1649).
[23] Long, D., & Fox, M. (2003a). The 3rd international planning competition: results and analysis. Journal of Artificial Intelligence Research, 20, 1–59. · Zbl 1036.68097 · doi:10.1023/A:1026044009832
[24] Long, D., & Fox, M. (2003b). PDDL2.1: an extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research, 20, 61–124. · Zbl 1036.68093
[25] Marín, R., Cárdenas, M., Balsa, M., & Sánchez, J. (1997). Obtaining solutions in fuzzy constraint networks. International Journal of Approximate Reasoning, 16, 261–288. · Zbl 0939.68116 · doi:10.1016/S0888-613X(96)00125-9
[26] Morris, P., & Muscettola, N. (2000). Execution of temporal plans with uncertainty. In AAAI 2000 (pp. 491–496).
[27] Munoz-Avila, H., Aha, D. W., Breslow, L., & Nau, D. (1999). HICAP: an interactive case-based planning architecture and its application to noncombatant evacuation operations. In Ninth conference on innovative applications of artificial intelligence (pp. 879–885). AAAI Press.
[28] Muscettola, N. (1994). HSTS: integrating planning and scheduling. In M. Zweben & M. Fox (Eds.), Intelligent scheduling (pp. 169–212). Morgan Kaufmann.
[29] Muscettola, N., Morris, P., & Tsamardinos, I. (1998). Reformulating temporal plans for efficient execution. In 6th conf. on principles of knowledge representation and reasoning (pp. 444–452).
[30] Myers, K. L. (1999). CPEF: A continuous planning and execution framework. AI Magazine, 20(4), 63–69.
[31] Penberthy, J., & Weld, D. (1994). Temporal planning with continous change. In AAAI’94 (pp. 1010–1015).
[32] Smith, D., & Weld, D. (1999). Temporal planning with mutual exclusion reasoning. In IJCAI’99 (pp. 326–337).
[33] Vidal, T., & Fargier, H. (1999). Handling contingency in temporal constraint networks: from consistency to controllabilities. Journal of Experimental and Theoretical Artificial Intelligence, 11, 23–45. · Zbl 1054.68664 · doi:10.1080/095281399146607
[34] Vila, L., & Godo, L. (1994a). On fuzzy temporal constraint networks. Mathware and Soft Computing, 3, 315–334. · Zbl 0833.68012
[35] Vila, L., & Godo, L. (1994b). Query answering in fuzzy temporal constraint networks. In IJCAI’95: Proceedings of the international joint conference on artificial intelligence (Vol. 3, pp. 315–334). · Zbl 0833.68012
[36] Weld, D. (1994). An introduction to least commitment planning. AI Magazine, 15(4), 27–61.
[37] Wilkins, D. E., & Desimone, R. V. (1994). Applying an AI plannet to military operations planning. In M. Zweben & M. S. Fox (Eds.), Intelligent scheduling. Morgan Kaufmann.
[38] Zadeh, L. (1978). Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems, 1, 3–28. · Zbl 0377.04002 · doi:10.1016/0165-0114(78)90029-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.