@InProceedings{Bercher2021POCLComplexities,
  author     = {Pascal Bercher},
  title      = {A Closer Look at Causal Links: Complexity Results for Delete-Relaxation in Partial Order Causal Link (POCL) Planning},
  booktitle  = {Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021)},
  year       = {2021},
  pages      = {36--45},
  publisher  = {AAAI Press},
  abstract   = {Partial Order Causal Link (POCL) planning follows the principle of least commitment in that it maintains only a partial order on its actions to prevent unnecessary early commitment during search. This can reduce the search space significantly by systematically representing up to an exponential number of action sequences in just a single search node. Progress on goal achievement is represented fully by this partial order and by causal links, which represent the causal relationships between these actions as well as between the initial state and goal. Plan existence for a state in classical planning thus corresponds to plan existence for a partial plan in POCL planning. Yet almost no theoretical investigations for POCL plan existence were conducted so far. While delete-relaxation makes plan existence tractable in classical planning, we show it to be NP-hard in POCL planning unless the current plan is totally ordered or causal links are almost completely ignored.},
  doi        = {10.1609/icaps.v31i1.15944},
  url_Paper  = {https://bercher.net/publications/2021/Bercher2021POCLComplexities.pdf},
  url_Slides = {https://bercher.net/publications/2021/Bercher2021POCLComplexitiesSlides.pdf},
  url_Poster = {https://bercher.net/publications/2021/Bercher2021POCLComplexitiesPoster.pdf},
  url_video_of_presentation  = {https://icaps21.icaps-conference.org/papers/exhibition_files/index_37.html}
}

{"_id":"B3by5hyeGjCJ8Qdjy","bibbaseid":"bercher-acloserlookatcausallinkscomplexityresultsfordeleterelaxationinpartialordercausallinkpoclplanning-2021","authorIDs":["qRXT9gMNhQE98wFSS"],"author_short":["Bercher, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]}],"title":"A Closer Look at Causal Links: Complexity Results for Delete-Relaxation in Partial Order Causal Link (POCL) Planning","booktitle":"Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021)","year":"2021","pages":"36–45","publisher":"AAAI Press","abstract":"Partial Order Causal Link (POCL) planning follows the principle of least commitment in that it maintains only a partial order on its actions to prevent unnecessary early commitment during search. This can reduce the search space significantly by systematically representing up to an exponential number of action sequences in just a single search node. Progress on goal achievement is represented fully by this partial order and by causal links, which represent the causal relationships between these actions as well as between the initial state and goal. Plan existence for a state in classical planning thus corresponds to plan existence for a partial plan in POCL planning. Yet almost no theoretical investigations for POCL plan existence were conducted so far. While delete-relaxation makes plan existence tractable in classical planning, we show it to be NP-hard in POCL planning unless the current plan is totally ordered or causal links are almost completely ignored.","doi":"10.1609/icaps.v31i1.15944","url_paper":"https://bercher.net/publications/2021/Bercher2021POCLComplexities.pdf","url_slides":"https://bercher.net/publications/2021/Bercher2021POCLComplexitiesSlides.pdf","url_poster":"https://bercher.net/publications/2021/Bercher2021POCLComplexitiesPoster.pdf","url_video_of_presentation":"https://icaps21.icaps-conference.org/papers/exhibition_files/index_37.html","bibtex":"@InProceedings{Bercher2021POCLComplexities,\n author = {Pascal Bercher},\n title = {A Closer Look at Causal Links: Complexity Results for Delete-Relaxation in Partial Order Causal Link (POCL) Planning},\n booktitle = {Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021)},\n year = {2021},\n pages = {36--45},\n publisher = {AAAI Press},\n abstract = {Partial Order Causal Link (POCL) planning follows the principle of least commitment in that it maintains only a partial order on its actions to prevent unnecessary early commitment during search. This can reduce the search space significantly by systematically representing up to an exponential number of action sequences in just a single search node. Progress on goal achievement is represented fully by this partial order and by causal links, which represent the causal relationships between these actions as well as between the initial state and goal. Plan existence for a state in classical planning thus corresponds to plan existence for a partial plan in POCL planning. Yet almost no theoretical investigations for POCL plan existence were conducted so far. While delete-relaxation makes plan existence tractable in classical planning, we show it to be NP-hard in POCL planning unless the current plan is totally ordered or causal links are almost completely ignored.},\n doi = {10.1609/icaps.v31i1.15944},\n url_Paper = {https://bercher.net/publications/2021/Bercher2021POCLComplexities.pdf},\n url_Slides = {https://bercher.net/publications/2021/Bercher2021POCLComplexitiesSlides.pdf},\n url_Poster = {https://bercher.net/publications/2021/Bercher2021POCLComplexitiesPoster.pdf},\n url_video_of_presentation = {https://icaps21.icaps-conference.org/papers/exhibition_files/index_37.html}\n}\n\n\n","author_short":["Bercher, P."],"key":"Bercher2021POCLComplexities","id":"Bercher2021POCLComplexities","bibbaseid":"bercher-acloserlookatcausallinkscomplexityresultsfordeleterelaxationinpartialordercausallinkpoclplanning-2021","role":"author","urls":{" paper":"https://bercher.net/publications/2021/Bercher2021POCLComplexities.pdf"," slides":"https://bercher.net/publications/2021/Bercher2021POCLComplexitiesSlides.pdf"," poster":"https://bercher.net/publications/2021/Bercher2021POCLComplexitiesPoster.pdf"," video of presentation":"https://icaps21.icaps-conference.org/papers/exhibition_files/index_37.html"},"metadata":{"authorlinks":{"bercher, p":"https://bercher.net/my-publications/workshop-papers"}},"downloads":32},"bibtype":"inproceedings","biburl":"bercher.net/bibtex/conferences.bib","creationDate":"2021-02-17T00:12:23.625Z","downloads":32,"keywords":[],"search_terms":["closer","look","causal","links","complexity","results","delete","relaxation","partial","order","causal","link","pocl","planning","bercher"],"title":"A Closer Look at Causal Links: Complexity Results for Delete-Relaxation in Partial Order Causal Link (POCL) Planning","year":2021,"dataSources":["upePYbh3wGv9oDZcn","zKgS72cAu6Ez7npdh","9XFSFwTKSMi2nBTY6"]}