Optimal Temporal Plan Merging. Marcon dos Santos, G. & Adams, J. A. In International Conference on Autonomous Agents and Multiagent Systems, pages 851–859, Auckland, New Zealand, May, 2020. ![Optimal Temporal Plan Merging [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper abstract bibtex Agents can individually devise plans and coordinate to achieve common goals. Methods exist to factor planning problems into separate tasks and distribute the plan synthesis process, while reducing the overall planning complexity. However, merging distributedly generated plans becomes computationally costly when task plans are tightly coupled, and conflicts arise due to dependencies between plan actions. Existing methods either scale poorly as the number of agents and tasks increases, or do not minimize makespan, the overall time necessary to execute all tasks. A new algorithm, the Temporal Optimal Conflict Resolution Algorithm (TCRA*), is introduced to merge independently generated plans and optimally minimize the resulting makespan. A proof of optimality is provided and the algorithm is empirically evaluated across two heterogeneous multiagent domains against two baseline algorithms. The TCRA* results in better makespan across the problems solved, and a search relaxation constant allows the TCRA* to generate better plans with competitive processing time and memory usage.
@inproceedings{MarcondosSantos2020b,
abstract = {Agents can individually devise plans and coordinate to achieve common goals. Methods exist to factor planning problems into separate tasks and distribute the plan synthesis process, while reducing the overall planning complexity. However, merging distributedly generated plans becomes computationally costly when task plans are tightly coupled, and conflicts arise due to dependencies between plan actions. Existing methods either scale poorly as the number of agents and tasks increases, or do not minimize makespan, the overall time necessary to execute all tasks. A new algorithm, the Temporal Optimal Conflict Resolution Algorithm (TCRA*), is introduced to merge independently generated plans and optimally minimize the resulting makespan. A proof of optimality is provided and the algorithm is empirically evaluated across two heterogeneous multiagent domains against two baseline algorithms. The TCRA* results in better makespan across the problems solved, and a search relaxation constant allows the TCRA* to generate better plans with competitive processing time and memory usage.},
added-at = {2020-05-24T20:36:48.000+0200},
address = {Auckland, New Zealand},
author = {Marcon dos Santos, Gilberto and Adams, Julie A.},
biburl = {https://www.bibsonomy.org/bibtex/29ddc20acd02b6688719499428fa6e2c0/marcondg},
booktitle = {International Conference on Autonomous Agents and Multiagent Systems},
interhash = {9a641ba2aed56777e7b19878eb758f34},
intrahash = {9ddc20acd02b6688719499428fa6e2c0},
keywords = {mine},
month = may,
pages = {851--859},
timestamp = {2020-05-24T20:36:48.000+0200},
title = {Optimal Temporal Plan Merging},
url = {http://ifaamas.org/Proceedings/aamas2020/pdfs/p851.pdf},
year = 2020
}
Downloads: 0
{"_id":"dFQSEeZpqmPRDWqkv","bibbaseid":"marcondossantos-adams-optimaltemporalplanmerging-2020","authorIDs":["7Sc5xNbP2PB7c8Zyq","A7SQcPWieTaakSKEb","FhAogtvuJuqz7g6a8","Gybos3Y5tDZdPoGWC","YeD2dpgxizbQqg6No","cHDWjtksJjqNATbKL","juWWLMwAoKHaeqTXK","sTsrg8KtfpC8G9TZq","vnS9er97J463wKZSY"],"author_short":["Marcon dos Santos, G.","Adams, J. A."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","abstract":"Agents can individually devise plans and coordinate to achieve common goals. Methods exist to factor planning problems into separate tasks and distribute the plan synthesis process, while reducing the overall planning complexity. However, merging distributedly generated plans becomes computationally costly when task plans are tightly coupled, and conflicts arise due to dependencies between plan actions. Existing methods either scale poorly as the number of agents and tasks increases, or do not minimize makespan, the overall time necessary to execute all tasks. A new algorithm, the Temporal Optimal Conflict Resolution Algorithm (TCRA*), is introduced to merge independently generated plans and optimally minimize the resulting makespan. A proof of optimality is provided and the algorithm is empirically evaluated across two heterogeneous multiagent domains against two baseline algorithms. The TCRA* results in better makespan across the problems solved, and a search relaxation constant allows the TCRA* to generate better plans with competitive processing time and memory usage.","added-at":"2020-05-24T20:36:48.000+0200","address":"Auckland, New Zealand","author":[{"propositions":["Marcon","dos"],"lastnames":["Santos"],"firstnames":["Gilberto"],"suffixes":[]},{"propositions":[],"lastnames":["Adams"],"firstnames":["Julie","A."],"suffixes":[]}],"biburl":"https://www.bibsonomy.org/bibtex/29ddc20acd02b6688719499428fa6e2c0/marcondg","booktitle":"International Conference on Autonomous Agents and Multiagent Systems","interhash":"9a641ba2aed56777e7b19878eb758f34","intrahash":"9ddc20acd02b6688719499428fa6e2c0","keywords":"mine","month":"May","pages":"851–859","timestamp":"2020-05-24T20:36:48.000+0200","title":"Optimal Temporal Plan Merging","url":"http://ifaamas.org/Proceedings/aamas2020/pdfs/p851.pdf","year":"2020","bibtex":"@inproceedings{MarcondosSantos2020b,\n abstract = {Agents can individually devise plans and coordinate to achieve common goals. Methods exist to factor planning problems into separate tasks and distribute the plan synthesis process, while reducing the overall planning complexity. However, merging distributedly generated plans becomes computationally costly when task plans are tightly coupled, and conflicts arise due to dependencies between plan actions. Existing methods either scale poorly as the number of agents and tasks increases, or do not minimize makespan, the overall time necessary to execute all tasks. A new algorithm, the Temporal Optimal Conflict Resolution Algorithm (TCRA*), is introduced to merge independently generated plans and optimally minimize the resulting makespan. A proof of optimality is provided and the algorithm is empirically evaluated across two heterogeneous multiagent domains against two baseline algorithms. The TCRA* results in better makespan across the problems solved, and a search relaxation constant allows the TCRA* to generate better plans with competitive processing time and memory usage.},\n added-at = {2020-05-24T20:36:48.000+0200},\n address = {Auckland, New Zealand},\n author = {Marcon dos Santos, Gilberto and Adams, Julie A.},\n biburl = {https://www.bibsonomy.org/bibtex/29ddc20acd02b6688719499428fa6e2c0/marcondg},\n booktitle = {International Conference on Autonomous Agents and Multiagent Systems},\n interhash = {9a641ba2aed56777e7b19878eb758f34},\n intrahash = {9ddc20acd02b6688719499428fa6e2c0},\n keywords = {mine},\n month = may,\n pages = {851--859},\n timestamp = {2020-05-24T20:36:48.000+0200},\n title = {Optimal Temporal Plan Merging},\n url = {http://ifaamas.org/Proceedings/aamas2020/pdfs/p851.pdf},\n year = 2020\n}\n\n","author_short":["Marcon dos Santos, G.","Adams, J. A."],"key":"MarcondosSantos2020b","id":"MarcondosSantos2020b","bibbaseid":"marcondossantos-adams-optimaltemporalplanmerging-2020","role":"author","urls":{"Paper":"http://ifaamas.org/Proceedings/aamas2020/pdfs/p851.pdf"},"keyword":["mine"],"metadata":{"authorlinks":{"marcon dos santos, g":"https://bibbase.org/show?bib=gilbertomarcon.com/bib/bib.bib"}}},"bibtype":"inproceedings","biburl":"gilbertomarcon.com/bib/bib.bib","creationDate":"2020-01-15T17:51:53.165Z","downloads":2,"keywords":["mine"],"search_terms":["optimal","temporal","plan","merging","marcon dos santos","adams"],"title":"Optimal Temporal Plan Merging","year":2020,"dataSources":["69vK5dhRWDkXbjroe","KmdEXRiKqSHvuDHgs","oD7FHzhaHxPuTH44c","EnSTqyuZDQaHMJc2b"]}