Anytime Focal Search with Applications. Cohen, L., Greco, M., Ma, H., Hernandez, C., Felner, A., Kumar, S., & Koenig, S. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 1434–1441, 2018. abstract bibtex Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*, it uses an open list whose states are sorted in increasing order of their f-values. Unlike A*, it also uses a focal list containing all states from the open list whose f-values are no larger than a suboptimality factor times the smallest f-value in the open list. In this paper, we develop an anytime version of FS, called anytime FS (AFS), that is useful when deliberation time is limited. AFS finds a 'good' solution quickly and refines it to better and better solutions if time allows. It does this refinement efficiently by reusing previous search efforts. On the theoretical side, we show that AFS is bounded suboptimal and that anytime potential search (ATPS/ANA*), a state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special case of AFS. In doing so, we bridge the gap between anytime search algorithms based on BSS and BCS. We also identify different properties of priority functions, used to sort the focal list, that may allow for efficient reuse of previous search efforts. On the experimental side, we demonstrate the usefulness of AFS for solving hard combinatorial problems, such as the generalized covering traveling salesman problem and the multi-agent pathfinding problem.
@INPROCEEDINGS{SKoen18p,
AUTHOR= "L. Cohen and M. Greco and H. Ma and C. Hernandez and A. Felner and S. Kumar and S. Koenig",
TITLE= "Anytime Focal Search with Applications",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
YEAR= "2018",
PAGES= "1434--1441",
PDF= "http://idm-lab.org/bib/abstracts/papers/ijcai18c.pdf",
FLAGS= ":2018:,:svenkoenig:,:lironcohen:,:hangma:,:satishkumar:,:arielfelner:",
ABSTRACT=
"Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*,
it uses an open list whose states are sorted in increasing order of their
f-values. Unlike A*, it also uses a focal list containing all states from
the open list whose f-values are no larger than a suboptimality factor times
the smallest f-value in the open list. In this paper, we develop an anytime
version of FS, called anytime FS (AFS), that is useful when deliberation time
is limited. AFS finds a 'good' solution quickly and refines it to better and
better solutions if time allows. It does this refinement efficiently by
reusing previous search efforts. On the theoretical side, we show that AFS is
bounded suboptimal and that anytime potential search (ATPS/ANA*), a
state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special
case of AFS. In doing so, we bridge the gap between anytime search algorithms
based on BSS and BCS. We also identify different properties of priority
functions, used to sort the focal list, that may allow for efficient reuse of
previous search efforts. On the experimental side, we demonstrate the
usefulness of AFS for solving hard combinatorial problems, such as the
generalized covering traveling salesman problem and the multi-agent
pathfinding problem."
}
Downloads: 0
{"_id":"FzJaQtoeF5wfBt63n","bibbaseid":"cohen-greco-ma-hernandez-felner-kumar-koenig-anytimefocalsearchwithapplications-2018","authorIDs":[],"author_short":["Cohen, L.","Greco, M.","Ma, H.","Hernandez, C.","Felner, A.","Kumar, S.","Koenig, S."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["L."],"propositions":[],"lastnames":["Cohen"],"suffixes":[]},{"firstnames":["M."],"propositions":[],"lastnames":["Greco"],"suffixes":[]},{"firstnames":["H."],"propositions":[],"lastnames":["Ma"],"suffixes":[]},{"firstnames":["C."],"propositions":[],"lastnames":["Hernandez"],"suffixes":[]},{"firstnames":["A."],"propositions":[],"lastnames":["Felner"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Kumar"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Koenig"],"suffixes":[]}],"title":"Anytime Focal Search with Applications","booktitle":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)","year":"2018","pages":"1434–1441","pdf":"http://idm-lab.org/bib/abstracts/papers/ijcai18c.pdf","flags":":2018:,:svenkoenig:,:lironcohen:,:hangma:,:satishkumar:,:arielfelner:","abstract":"Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*, it uses an open list whose states are sorted in increasing order of their f-values. Unlike A*, it also uses a focal list containing all states from the open list whose f-values are no larger than a suboptimality factor times the smallest f-value in the open list. In this paper, we develop an anytime version of FS, called anytime FS (AFS), that is useful when deliberation time is limited. AFS finds a 'good' solution quickly and refines it to better and better solutions if time allows. It does this refinement efficiently by reusing previous search efforts. On the theoretical side, we show that AFS is bounded suboptimal and that anytime potential search (ATPS/ANA*), a state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special case of AFS. In doing so, we bridge the gap between anytime search algorithms based on BSS and BCS. We also identify different properties of priority functions, used to sort the focal list, that may allow for efficient reuse of previous search efforts. On the experimental side, we demonstrate the usefulness of AFS for solving hard combinatorial problems, such as the generalized covering traveling salesman problem and the multi-agent pathfinding problem.","bibtex":"@INPROCEEDINGS{SKoen18p, \n AUTHOR= \"L. Cohen and M. Greco and H. Ma and C. Hernandez and A. Felner and S. Kumar and S. Koenig\",\n TITLE= \"Anytime Focal Search with Applications\",\n BOOKTITLE= \"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)\",\n YEAR= \"2018\",\n PAGES= \"1434--1441\",\n PDF= \"http://idm-lab.org/bib/abstracts/papers/ijcai18c.pdf\",\n FLAGS= \":2018:,:svenkoenig:,:lironcohen:,:hangma:,:satishkumar:,:arielfelner:\",\n ABSTRACT= \n\"Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*,\nit uses an open list whose states are sorted in increasing order of their\nf-values. Unlike A*, it also uses a focal list containing all states from\nthe open list whose f-values are no larger than a suboptimality factor times\nthe smallest f-value in the open list. In this paper, we develop an anytime\nversion of FS, called anytime FS (AFS), that is useful when deliberation time\nis limited. AFS finds a 'good' solution quickly and refines it to better and\nbetter solutions if time allows. It does this refinement efficiently by\nreusing previous search efforts. On the theoretical side, we show that AFS is\nbounded suboptimal and that anytime potential search (ATPS/ANA*), a\nstate-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special\ncase of AFS. In doing so, we bridge the gap between anytime search algorithms\nbased on BSS and BCS. We also identify different properties of priority\nfunctions, used to sort the focal list, that may allow for efficient reuse of\nprevious search efforts. On the experimental side, we demonstrate the\nusefulness of AFS for solving hard combinatorial problems, such as the\ngeneralized covering traveling salesman problem and the multi-agent\npathfinding problem.\"\n}\n\n","author_short":["Cohen, L.","Greco, M.","Ma, H.","Hernandez, C.","Felner, A.","Kumar, S.","Koenig, S."],"key":"SKoen18p","id":"SKoen18p","bibbaseid":"cohen-greco-ma-hernandez-felner-kumar-koenig-anytimefocalsearchwithapplications-2018","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://mapf.info/bib/mapf.bib","creationDate":"2019-05-05T18:02:17.679Z","downloads":0,"keywords":[],"search_terms":["anytime","focal","search","applications","cohen","greco","ma","hernandez","felner","kumar","koenig"],"title":"Anytime Focal Search with Applications","year":2018,"dataSources":["oEkRzPPMbrG9LyYPh"]}