{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T14:24:30Z","timestamp":1780064670496,"version":"3.54.0"},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Artif. Intell. Tools"],"published-print":{"date-parts":[[2004,12]]},"abstract":"<jats:p> We study in this paper the partitioning of the constraints of a temporal planning problem by subgoals, their sequential evaluation before parallelizing the actions, and the resolution of inconsistent global constraints across subgoals. Using an \u2113<jats:sub>1<\/jats:sub>-penalty formulation and the theory of extended saddle points, we propose a global-search strategy that looks for local minima in the original-variable space of the \u2113<jats:sub>1<\/jats:sub>-penalty function and for local maxima in the penalty space. Our approach improves over a previous scheme that partitions constraints along the temporal horizon. The previous scheme leads to many global constraints that relate states in adjacent stages, which means that an incorrect assignment of states in an earlier stage of the horizon may violate a global constraint in a later stage of the horizon. To resolve the violated global constraint in this case, state changes will need to propagate sequentially through multiple stages, often leading to a search that gets stuck in an infeasible point for an extended period of time. In this paper, we propose to partition all the constraints by subgoals and to add new global constraints in order to ensure that state assignments of a subgoal are consistent with those in other subgoals. Such an approach allows the information on incorrect state assignments in one subgoal to propagate quickly to other subgoals. Using MIPS as the basic planner in a partitioned implementation, we demonstrate significant improvements in time and quality in solving some PDDL2.1 benchmark problems. <\/jats:p>","DOI":"10.1142\/s0218213004001806","type":"journal-article","created":{"date-parts":[[2004,12,28]],"date-time":"2004-12-28T12:24:48Z","timestamp":1104236688000},"page":"767-790","source":"Crossref","is-referenced-by-count":8,"title":["SUBGOAL PARTITIONING AND GLOBAL SEARCH FOR SOLVING TEMPORAL PLANNING PROBLEMS IN MIXED SPACE"],"prefix":"10.1142","volume":"13","author":[{"given":"BENJAMIN W.","family":"WAH","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering and the Coordinated Science Laboratory, University of Illinois, Urbana-Champaign, Urbana, IL 61801, United States of America"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"YIXIN","family":"CHEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science and the Coordinated Science Laboratory, University of Illinois, Urbana-Champaign, Urbana, IL 61801, United States of America"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","volume-title":"Simulated Annealing and Boltzmann Machines","author":"Aarts E.","year":"1989"},{"key":"rf2","volume-title":"Nonlinear Programming: Analysis and Methods","author":"Avriel M.","year":"1976"},{"key":"rf3","volume-title":"Nonlinear Programming","author":"Bertsekas D. P.","year":"1999"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00047-1"},{"key":"rf5","volume":"129","author":"Bonet B.","journal-title":"Artificial Intelligence, Special issue on Heuristic Search"},{"key":"rf14","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1613\/jair.855","volume":"14","author":"Hoffmann J.","journal-title":"J. of Artificial Intelligence Research"},{"key":"rf15","volume-title":"Proc. 2nd Int'l NASA Workshop on Planning and Scheduling for Space","author":"Jonsson A. K.","year":"2000"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888900001053"},{"key":"rf19","first-page":"339","volume":"12","author":"Koehler J.","journal-title":"J. of AI Research"},{"key":"rf20","first-page":"73","author":"Lin F.","journal-title":"AI Magazine"},{"key":"rf21","author":"Long D.","journal-title":"J. of AI Research (JAIR)"},{"key":"rf23","series-title":"Technical report","volume-title":"AltAlt: Combining the advantages of Graphplan and heuristic state search","author":"Nigenda R. S.","year":"2000"},{"key":"rf25","unstructured":"J.\u00a0Penberethy and D.\u00a0Weld, Proc. 12th National Conf. on AI (AAAI, 1994)\u00a0pp. 1010\u20131015."},{"key":"rf26","volume-title":"Optimization in Operations Research","author":"Rardin R. L.","year":"1998"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888900001089"},{"key":"rf29","series-title":"Technical report","volume-title":"Sapa: A domain-independent heuristic metric temporal planner","author":"Subbarao M. B. D.","year":"2002"},{"key":"rf34","volume":"15","author":"Wolfman S.","journal-title":"The Knowledge Engineering Review"}],"container-title":["International Journal on Artificial Intelligence Tools"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218213004001806","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T16:52:33Z","timestamp":1565196753000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218213004001806"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12]]},"references-count":17,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2004,12]]}},"alternative-id":["10.1142\/S0218213004001806"],"URL":"https:\/\/doi.org\/10.1142\/s0218213004001806","relation":{},"ISSN":["0218-2130","1793-6349"],"issn-type":[{"value":"0218-2130","type":"print"},{"value":"1793-6349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,12]]}}}