Temporal planning through mixed integer programming: A preliminary report
Date
2002ISSN
0302-9743Source
8th International Conference on Principles and Practice of Constraint Programming, CP 2002Volume
2470Pages
47-62Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
Temporal planning is an important problem, as in many real world planning domains actions have different durations and the goals should be achieved by a specified deadline, or as soon as possible. This paper presents a novel approach to temporal planning that is based on Mixed Integer Programming. In the new framework, a temporal planning domain is modeled by two sets of linear inequalities. The first set involves integer variables and is a Graphplan-like encoding of a simplification of the original problem where the duration of the actions is ignored. The second set involves both integer and real valued variables, and models the temporal aspects of the problem. The two sets interact through the common integer variables, and their combination can be solved by using available Mixed Integer Programming software. The new method aims at generating good solutions quickly, under different minimization objectives.Preliminary experimental results illustrate the effectiveness of our approach. © Springer-Verlag Berlin Heidelberg 2002.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Conference Object
Optimal wavelength allocation and flow assignment in multiwavelength optical networks
Kabranov, O.; Makrakis, D.; Charalambous, Charalambos D.; Ionescu, D. (2001)Automatically Switched Optical Networks (ASON) require a control strategy that determines the optimal distribution of flows over different wavelengths. Such strategy will increase the profit, by allowing service providers ...
-
Article
Fault model identification and synthesis in Petri nets
Cabasino, M. P.; Giua, A.; Hadjicostis, Christoforos N.; Seatzu, C. (2015)Fault identification studies in the Discrete Event Systems literature are typically model-based and require knowledge of the structure of the system, including the nature (and behavior) of the possible faults. In this paper ...
-
Conference Object
Integer programs and valid inequalities for planning problems
Bockmayr, A.; Dimopoulos, Yannis (Springer Verlag, 2000)Part of the recent work in AI planning is concerned with the development of algorithms that regard planning as a combinato-rial search problem. The underlying representation language is basically propositional logic. While ...