{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T06:54:51Z","timestamp":1790146491048,"version":"4.0.1"},"reference-count":41,"publisher":"SAGE Publications","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIC"],"published-print":{"date-parts":[[2017,12,1]]},"DOI":"10.3233\/aic-170743","type":"journal-article","created":{"date-parts":[[2017,11,14]],"date-time":"2017-11-14T11:16:03Z","timestamp":1510658163000},"page":"393-418","source":"Crossref","is-referenced-by-count":1,"title":["The compressed differential heuristic"],"prefix":"10.1177","volume":"30","author":[{"given":"Meir","family":"Goldenberg","sequence":"first","affiliation":[{"name":"The Jerusalem College of Technology, Jerusalem, Israel. E-mail:\u00a0mgoldenbe@gmail.com"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ariel","family":"Felner","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Be\u2019er-Sheva, Israel. E-mails:\u00a0felner@bgu.ac.il,\u00a0palomboalon@gmail.com"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alon","family":"Palombo","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Be\u2019er-Sheva, Israel. E-mails:\u00a0felner@bgu.ac.il,\u00a0palomboalon@gmail.com"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathan","family":"Sturtevant","sequence":"additional","affiliation":[{"name":"The University of Denver, Denver, USA. E-mail:\u00a0Sturtevant@cs.du.edu"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Schaeffer","sequence":"additional","affiliation":[{"name":"The University of Alberta, Edmonton, Canada. E-mail:\u00a0jonathan@cs.ualberta.ca"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","reference":[{"key":"10.3233\/AIC-170743_ref1","doi-asserted-by":"crossref","unstructured":"I.\u00a0Abraham, D.\u00a0Delling, A.V.\u00a0Goldberg and R.F.F.\u00a0Werneck, Hierarchical hub labelings for shortest paths, in: European Symposium on Algorithms, 2012, pp.\u00a024\u201335.","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"10.3233\/AIC-170743_ref2","doi-asserted-by":"crossref","unstructured":"T.\u00a0Akiba, Y.\u00a0Iwata and Y.\u00a0Yoshida, Fast exact shortest-path distance queries on large networks by pruned landmark labeling, in: SIGMOD International Conference on Management of Data, 2013, pp.\u00a0349\u2013360.","DOI":"10.1145\/2463676.2465315"},{"issue":"4","key":"10.3233\/AIC-170743_ref3","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/235815.235821","article-title":"The quickhull algorithm for convex hulls","volume":"22","author":"Barber","year":"1996","journal-title":"ACM Transactions On Mathematical Software"},{"key":"10.3233\/AIC-170743_ref4","doi-asserted-by":"crossref","unstructured":"H.\u00a0Bast, S.\u00a0Funke, D.\u00a0Matijevic, P.\u00a0Sanders and D.\u00a0Schultes, In transit to constant time shortest-path queries in road networks, in: The Workshop on Algorithm Engineering and Experiments, 2007.","DOI":"10.1137\/1.9781611972870.5"},{"key":"10.3233\/AIC-170743_ref5","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1613\/jair.3076","article-title":"Case-based subgoaling in real-time heuristic search for video game pathfinding","volume":"39","author":"Bulitko","year":"2010","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"10.3233\/AIC-170743_ref6","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1613\/jair.2497","article-title":"Dynamic control in real-time heuristic search","volume":"32","author":"Bulitko","year":"2008","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"issue":"3","key":"10.3233\/AIC-170743_ref7","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1111\/0824-7935.00065","article-title":"Pattern databases","volume":"14","author":"Culberson","year":"1998","journal-title":"Computational Intelligence"},{"key":"10.3233\/AIC-170743_ref8","unstructured":"A.\u00a0Felner, M.\u00a0Berrer, N.\u00a0Sturtevant and J.\u00a0Schaeffer, Abstraction-based heuristics with true distance computations, in: SARA, 2009."},{"key":"10.3233\/AIC-170743_ref9","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1613\/jair.1480","article-title":"Additive pattern database heuristics","volume":"22","author":"Felner","year":"2004","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"10.3233\/AIC-170743_ref10","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1613\/jair.2241","article-title":"Compressed pattern databases","volume":"30","author":"Felner","year":"2007","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"10.3233\/AIC-170743_ref11","unstructured":"A.\u00a0Felner, R.\u00a0Meshulam, R.C.\u00a0Holte and R.E.\u00a0Korf, Compressing pattern databases, in: AAAI, 2004, pp.\u00a0638\u2013643."},{"issue":"9\u201310","key":"10.3233\/AIC-170743_ref12","doi-asserted-by":"publisher","first-page":"1570","DOI":"10.1016\/j.artint.2011.02.001","article-title":"Inconsistent heuristics in theory and practice","volume":"175","author":"Felner","year":"2011","journal-title":"Artificial Intelligence"},{"key":"10.3233\/AIC-170743_ref13","unstructured":"A.\u00a0Felner, U.\u00a0Zahavi, J.\u00a0Schaeffer and R.C.\u00a0Holte, Dual lookups in pattern databases, in: IJCAI, 2005, pp.\u00a0103\u2013108."},{"key":"10.3233\/AIC-170743_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"10.3233\/AIC-170743_ref15","doi-asserted-by":"crossref","unstructured":"A.\u00a0Goldberg, H.\u00a0Kaplan and R.\u00a0Werneck, Reach for A*: Shortest path algorithms with preprocessing, in: Ninth DIMACS Implementation Challenge, 2009, pp.\u00a093\u2013140.","DOI":"10.1090\/dimacs\/074\/05"},{"key":"10.3233\/AIC-170743_ref16","unstructured":"A.\u00a0Goldberg and R.\u00a0Werneck, Computing point-to-point shortest paths from external memory, in: ALENEX, 2005, pp.\u00a026\u201340. ISBN 0-89871-596-2."},{"key":"10.3233\/AIC-170743_ref17","unstructured":"A.V.\u00a0Goldberg and C.\u00a0Harrelson, Computing the shortest path: A* search meets graph theory, in: SODA, 2005, pp.\u00a0156\u2013165."},{"key":"10.3233\/AIC-170743_ref18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.knosys.2017.05.009","article-title":"The heuristic search research framework","volume":"129","author":"Goldenberg","year":"2017","journal-title":"Knowledge-Based Systems"},{"key":"10.3233\/AIC-170743_ref19","doi-asserted-by":"crossref","unstructured":"M.\u00a0Goldenberg, A.\u00a0Felner, N.\u00a0Sturtevant and J.\u00a0Schaeffer, Portal-based true-distance heuristics for path finding, in: International Symposium on Combinatorial Search (SoCS), 2010.","DOI":"10.1609\/socs.v1i1.18169"},{"key":"10.3233\/AIC-170743_ref20","doi-asserted-by":"crossref","unstructured":"M.\u00a0Goldenberg, N.R.\u00a0Sturtevant, A.\u00a0Felner and J.\u00a0Schaeffer, The compressed differential heuristic, in: AAAI, 2011.","DOI":"10.1609\/aaai.v25i1.7823"},{"key":"10.3233\/AIC-170743_ref21","unstructured":"J.E.\u00a0Guivant, B.\u00a0Seton and M.A.\u00a0Whitty, 2d path planning based on Dijkstra\u2019s algorithm and pseudo priority queues, in: International Symposium on Combinatorial Search (SoCS), 2012."},{"key":"10.3233\/AIC-170743_ref22","doi-asserted-by":"crossref","unstructured":"D.D.\u00a0Harabor and A.\u00a0Grastien, Online graph pruning for pathfinding on grid maps, in: AAAI, 2011.","DOI":"10.1609\/aaai.v25i1.7994"},{"issue":"2","key":"10.3233\/AIC-170743_ref23","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"key":"10.3233\/AIC-170743_ref24","doi-asserted-by":"crossref","unstructured":"M.\u00a0Hatem and W.\u00a0Ruml, Simpler bounded suboptimal search, in: AAAI, 2014, pp.\u00a0856\u2013862.","DOI":"10.1609\/aaai.v28i1.8846"},{"key":"10.3233\/AIC-170743_ref25","unstructured":"M.\u00a0Helmert, P.\u00a0Haslum and J.\u00a0Hoffmann, Flexible abstraction heuristics for optimal sequential planning, in: ICAPS, 2007, pp.\u00a0176\u2013183."},{"issue":"1","key":"10.3233\/AIC-170743_ref26","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0004-3702(84)90003-1","article-title":"A heuristic search algorithm with modifiable estimate","volume":"23","author":"M\u00e9ro","year":"1984","journal-title":"Artificial Intelligence"},{"key":"10.3233\/AIC-170743_ref27","doi-asserted-by":"crossref","unstructured":"T.\u00a0Ng and H.\u00a0Zhang, Predicting Internet network distance with coordinates-based approaches, in: INFOCOM, 2002, pp.\u00a0170\u2013179.","DOI":"10.1109\/INFCOM.2002.1019258"},{"key":"10.3233\/AIC-170743_ref28","unstructured":"I.\u00a0Pohl, The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving, in: IJCAI, 1973, pp.\u00a012\u201317."},{"key":"10.3233\/AIC-170743_ref29","doi-asserted-by":"crossref","unstructured":"D.C.\u00a0Rayner, M.H.\u00a0Bowling and N.R.\u00a0Sturtevant, Euclidean heuristic optimization, in: AAAI, 2011.","DOI":"10.1609\/aaai.v25i1.7815"},{"key":"10.3233\/AIC-170743_ref30","unstructured":"D.C.\u00a0Rayner, N.R.\u00a0Sturtevant and M.\u00a0Bowling, Subset selection of search heuristics, in: IJCAI, 2013."},{"key":"10.3233\/AIC-170743_ref31","unstructured":"G.\u00a0Sharon, A.\u00a0Felner and N.R.\u00a0Sturtevant, Exponential deepening A* for real-time agent-centered search, in: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27\u201331, 2014, Qu\u00e9bec City, Qu\u00e9bec, Canada, 2014, pp.\u00a0871\u2013877, http:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI14\/paper\/view\/8216."},{"key":"10.3233\/AIC-170743_ref32","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1613\/jair.4931","article-title":"Compressing optimal paths with run length encoding","volume":"54","author":"Strasser","year":"2015","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"10.3233\/AIC-170743_ref33","unstructured":"N.\u00a0Sturtevant, A.\u00a0Felner, M.\u00a0Barer, J.\u00a0Schaeffer and N.\u00a0Burch, Memory-based heuristics for explicit state spaces, in: IJCAI, 2009, pp.\u00a0609\u2013614."},{"issue":"2","key":"10.3233\/AIC-170743_ref34","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1109\/TCIAIG.2012.2197681","article-title":"Benchmarks for grid-based pathfinding","volume":"4","author":"Sturtevant","year":"2012","journal-title":"IEEE Transactions on Computational Intelligence and AI in Games (T-CIAIG)"},{"issue":"3","key":"10.3233\/AIC-170743_ref35","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1609\/aimag.v35i3.2547","article-title":"The grid-based path-planning competition","volume":"35","author":"Sturtevant","year":"2014","journal-title":"AI Magazine"},{"key":"10.3233\/AIC-170743_ref36","unstructured":"N.R.\u00a0Sturtevant and V.\u00a0Bulitko, Reaching the goal in real-time heuristic search: Scrubbing behavior is unavoidable, in: Proceedings of the Seventh Annual Symposium on Combinatorial Search (SOCS), August 15\u201317, 2014, Prague, Czech Republic, 2014, http:\/\/www.aaai.org\/ocs\/index.php\/SOCS\/SOCS14\/paper\/view\/8941."},{"issue":"3","key":"10.3233\/AIC-170743_ref37","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1109\/TCIAIG.2015.2421493","article-title":"Optimization using boundary lookup jump point search","volume":"8","author":"Traish","year":"2015","journal-title":"IEEE Transactions on Computational Intelligence and AI in Games (T-CIAIG)"},{"key":"10.3233\/AIC-170743_ref38","doi-asserted-by":"crossref","unstructured":"T.\u00a0Uras and S.\u00a0Koenig, Identifying hierarchies for fast optimal search, in: AAAI Conference on Artificial Intelligence, 2014, pp.\u00a0878\u2013884.","DOI":"10.1609\/aaai.v28i1.8845"},{"key":"10.3233\/AIC-170743_ref39","unstructured":"T.\u00a0Uras, S.\u00a0Koenig and C.\u00a0Hern\u00e1ndez, Subgoal graphs for eight-neighbor gridworlds, in: International Symposium on Combinatorial Search (SoCS), 2012."},{"key":"10.3233\/AIC-170743_ref40","unstructured":"F.\u00a0Xie, A.\u00a0Botea and A.\u00a0Kishimoto, Heuristic-aided compressed distance databases, in: AAAI Workshop on Planning, Search and Optimization, 2015."},{"key":"10.3233\/AIC-170743_ref41","unstructured":"Z.\u00a0Zhang, N.\u00a0Sturtevant, R.\u00a0Holte, J.\u00a0Schaeffer and A.\u00a0Felner, A* search with inconsistent heuristics, in: IJCAI, 2009, pp.\u00a0634\u2013639, http:\/\/portal.acm.org\/citation.cfm?id=1661445.1661546."}],"container-title":["AI Communications"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/AIC-170743","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T18:27:43Z","timestamp":1777400863000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/AIC-170743"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,1]]},"references-count":41,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.3233\/aic-170743","relation":{},"ISSN":["1875-8452","0921-7126"],"issn-type":[{"value":"1875-8452","type":"electronic"},{"value":"0921-7126","type":"print"}],"subject":[],"published":{"date-parts":[[2017,12,1]]}}}