{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T07:37:51Z","timestamp":1773733071042,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,4,21]],"date-time":"2012-04-21T00:00:00Z","timestamp":1334966400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s10458-012-9195-8","type":"journal-article","created":{"date-parts":[[2012,4,20]],"date-time":"2012-04-20T00:35:36Z","timestamp":1334882136000},"page":"354-388","source":"Crossref","is-referenced-by-count":8,"title":["Field D* path-finding on weighted triangulated and tetrahedral meshes"],"prefix":"10.1007","volume":"26","author":[{"given":"Simon","family":"Perkins","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Marais","sequence":"additional","affiliation":[]},{"given":"James","family":"Gain","sequence":"additional","affiliation":[]},{"given":"Mark","family":"Berman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,4,21]]},"reference":[{"key":"9195_CR1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. Djikstra","year":"1959","unstructured":"Djikstra E. (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1: 269\u2013271","journal-title":"Numerische Mathematik"},{"issue":"2","key":"9195_CR2","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P. Hart","year":"1968","unstructured":"Hart P., Nilsson N., Raphael B. (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4(2): 100\u2013107","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"key":"9195_CR3","volume-title":"Principles of artificial intelligence","author":"N.J. Nilsson","year":"1993","unstructured":"Nilsson N.J. (1993) Principles of artificial intelligence. Morgan Kaufmann Publishers, San Francisco"},{"key":"9195_CR4","doi-asserted-by":"crossref","unstructured":"Mitchell, J. S. B., & Papadimitriou, C. H. (1991). The weighted region problem: Finding shortest paths through a weighted planar subdivision. Journal of the ACM, 38(1), 18\u201373. http:\/\/doi.acm.org\/10.1145\/102782.102784 .","DOI":"10.1145\/102782.102784"},{"key":"9195_CR5","unstructured":"Mata, C. S., & Mitchell, J. S. B. (1997). A new algorithm for computing shortest paths in weighted planar subdivisions (extended abstract). In Proceedings of the thirteenth annual symposium on computational geometry, SCG \u201997 (pp. 264\u2013273). New York: ACM. http:\/\/doi.acm.org\/10.1145\/262839.262983 ."},{"key":"9195_CR6","doi-asserted-by":"crossref","unstructured":"Lanthier, M., Maheshwari, A., & Sack, J. R. (1997). Approximating weighted shortest paths on polyhedral surfaces. In Proceedings of the thirteenth annual symposium on computational geometry, SCG \u201997 (pp. 485\u2013486). New York: ACM. http:\/\/doi.acm.org\/10.1145\/262839.263101","DOI":"10.1145\/262839.262984"},{"key":"9195_CR7","doi-asserted-by":"crossref","unstructured":"Aleksandrov, L., Maheshwari, A., & Sack, J. R. (2000). Approximation algorithms for geometric shortest path problems. In Proceedings of the thirty-second annual ACM symposium on theory of computing, STOC \u201900 (pp. 286\u2013295). New York: ACM. http:\/\/doi.acm.org\/10.1145\/335305.335339","DOI":"10.1145\/335305.335339"},{"key":"9195_CR8","unstructured":"Sun, Z., & Reif, J. (2001). Bushwhack: An approximation algorithm for minimal paths through pseudo-euclidean spaces. In P. Eades, T. Takaoka (Eds.), Algorithms and computation. Lecture notes in computer science (Vol. 2223, pp. 160\u2013171). Berlin: Springer."},{"key":"9195_CR9","unstructured":"Sun, Z. S., & Reif, J. (2003). Adaptive and compact discretization for weighted regions optimal path finding. In Proceedings of 14th Symposium on fundamentals of computation theory LNCS (pp. 258\u2013270). New York: Springer."},{"key":"9195_CR10","unstructured":"Aleksandrov, L., Djidjev, H., Guo, H., Maheshwari, A., Nussbaum, D., & Sack, J. R. (2006). Approximate shortest path queries on weighted polyhedral surfaces. In R. Krlovic & P. Urzyczyn (Eds.), Mathematical foundations of computer science 2006. Lecture notes in computer science (Vol. 4162, pp. 98\u2013109). Berlin: Springer."},{"key":"9195_CR11","unstructured":"Cheng, S. W., Na, H. S., Vigneron, S., & Wang, Y. (2010). Querying approximate shortest paths in anisotropic regions. SIAM Journal on Computing, 39, 1888\u20131918. http:\/\/dx.doi.org\/10.1137\/08074216 .."},{"key":"9195_CR12","unstructured":"Ferguson, D., & Stentz, A. T. (2005). The Field D* algorithm for improved path planning and replanning in uniform and non-uniform cost environments. Tech. Rep. CMU-RI-TR-05-19, Robotics Institute, Pittsburgh."},{"key":"9195_CR13","unstructured":"Ferguson, D., & Stentz, A. (2006). Multi-resolution Field D*. In Proceedings of the international conference on intelligent autonomous systems (IAS)."},{"key":"9195_CR14","doi-asserted-by":"crossref","unstructured":"Samet, H. (1984). The quadtree and related hierarchical data structures. ACM Computing Surveys, 16(2), 187\u2013260. http:\/\/doi.acm.org\/10.1145\/356924.356930","DOI":"10.1145\/356924.356930"},{"key":"9195_CR15","doi-asserted-by":"crossref","unstructured":"Carsten, J., Ferguson, D., & Stentz, A. (2006). 3D Field D*: Improved Path Planning and Replanning in Three Dimensions. In IEEE\/RSJ international conference on intelligent robots and systems (pp. 3381\u20133386). doi: 10.1109\/IROS.2006.282516 .","DOI":"10.1109\/IROS.2006.282516"},{"key":"9195_CR16","unstructured":"Peucker, T. K., Fowler, R. J., Little, J. J., & Mark, D. M. (1978). The triangulated irregular network. In Proceedings, American Society for photogrammetry, digital terrain models symposium (Vol. 516, pp. 96\u2013103). St.Louis, Missouri."},{"key":"9195_CR17","unstructured":"Fowler, R. J., & Little, J. J. (1979). Automatic extraction of irregular network digital terrain models. In Proceedings of the 6th annual conference on computer graphics and interactive techniques, SIGGRAPH \u201979 (pp. 199\u2013207). New York: ACM."},{"key":"9195_CR18","unstructured":"Edelsbrunner, H., Ablowitz, M. J., Davis, S. H., Hinch, E. J., Iserles, A., Ockendon, J., & Olver, P. J. (2006). Geometry and topology for mesh generation. Cambridge monographs on applied and computational mathematics. New York: Cambridge University Press."},{"key":"9195_CR19","unstructured":"Shewchuk, J. R. (2002). What is a good linear element? Interpolation, conditioning, and quality measures. In Proceedings, 11th international meshing roundtable (pp. 115\u2013126)."},{"key":"9195_CR20","doi-asserted-by":"crossref","unstructured":"Konolige, K. (2000). A gradient method for realtime robot control. In International conference on intelligent robots and systems, 2000 (IROS 2000), Proceedings. IEEE\/RSJ (Vol. 1, pp. 639\u2013646). doi: 10.1109\/IROS.2000.894676 .","DOI":"10.1109\/IROS.2000.894676"},{"key":"9195_CR21","doi-asserted-by":"crossref","unstructured":"Philippsen, R., & Siegwart, R. (2005). An interpolated dynamic navigation function. In Proceedings of the IEEE international conference on robotics and automation (ICRA).","DOI":"10.1109\/ROBOT.2005.1570697"},{"key":"9195_CR22","doi-asserted-by":"crossref","first-page":"1591","DOI":"10.1073\/pnas.93.4.1591","volume":"93","author":"J.A. Sethian","year":"1995","unstructured":"Sethian J.A. (1995) A fast marching level set method for monotonically advancing fronts. Proceedings of the National Academy of Sciences of the United States of America 93: 1591\u20131595","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"key":"9195_CR23","first-page":"7","volume":"1","author":"A. Botea","year":"2004","unstructured":"Botea A., M\u00fcller M., Schaeffer J. (2004) Near optimal hierarchical path-finding. Journal of Game Development 1: 7\u201328","journal-title":"Journal of Game Development"},{"key":"9195_CR24","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1613\/jair.2994","volume":"39","author":"K. Daniel","year":"2010","unstructured":"Daniel K., Nash A., Koenig S., Felner A. (2010) Theta*: Any-angle path planning on grids. Journal of Artificial Intelligence (JAIR) 39: 533\u2013579","journal-title":"Journal of Artificial Intelligence (JAIR)"},{"key":"9195_CR25","unstructured":"Kallman, M. (2005). Path planning in triangulations. In Proceedings of the IJACI workshop on reasoning, representation and learning in computer games."},{"key":"9195_CR26","doi-asserted-by":"crossref","unstructured":"Chazelle, B. (1982). A Theorem on polygon cutting with applications. In SFCS \u201982: Proceedings of the 23rd annual symposium on foundations of computer science (pp. 339\u2013349). Washington, DC: IEEE Computer Society. http:\/\/dx.doi.org\/10.1109\/SFCS.1982.58 .","DOI":"10.1109\/SFCS.1982.58"},{"issue":"2","key":"9195_CR27","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1002\/rob.20109","volume":"23","author":"D. Ferguson","year":"2006","unstructured":"Ferguson D., Stentz A. T. (2006) Using interpolation to improve path planning: the Field D* algorithm. Journal of Field Robotics 23(2): 79\u2013101","journal-title":"Journal of Field Robotics"},{"key":"9195_CR28","doi-asserted-by":"crossref","unstructured":"Sapronov, L., & Lacaze, A. (2008). Path planning for robotic vehicles using Generalized Field D*. Proceedings of SPIE, 6962, 69621C. doi: 10.1117\/12.780650 .","DOI":"10.1117\/12.780650"},{"key":"9195_CR29","unstructured":"Stentz, A. (1995). The focussed d* algorithm for real-time replanning. In Proceedings of the 14th international joint conference on artificial intelligence (Vol. 2, pp. 1652\u20131659). San Francisco: Morgan Kaufmann Publishers Inc."},{"key":"9195_CR30","unstructured":"Koenig, S., & Likhachev, M. (2002a). Incremental A*. In Proceedings of the neural information processing systems. Cambridge, MA: MIT Press."},{"key":"9195_CR31","unstructured":"Koenig, S., & Likhachev, M. (2002b). D* Lite. In Eighteenth national conference on artificial intelligence (pp. 476\u2013483). Menlo Park, CA: American Association for Artificial Intelligence."},{"key":"9195_CR32","doi-asserted-by":"crossref","unstructured":"Choi, S., & Yu, W. (2011). Any-angle path planning on non-uniform costmaps. In IEEE international conference on robotics and automation (ICRA) (pp. 5615\u20135621). doi: 10.1109\/ICRA.2011.5979769 .","DOI":"10.1109\/ICRA.2011.5979769"},{"key":"9195_CR33","unstructured":"Shewchuk, J. R. (2000). Mesh Generation for domains with small angles. In SCG \u201900: proceedings of the sixteenth annual symposium on computational geometry (pp. 1\u201310). New York: ACM. http:\/\/doi.acm.org\/10.1145\/336154.336163 ."},{"key":"9195_CR34","unstructured":"Alliez, P., Rineau, L., Tayeb, S., Tournois, J., & Yvinec, M. (2011). 3D mesh generation. CGAL user and reference manual (3.9th ed.). CGAL Editorial Board. http:\/\/www.cgal.org\/Manual\/3.9\/doc_html\/cgal_manual\/packages.html#Pkg:Mesh_3 ."},{"key":"9195_CR35","unstructured":"Golias, N. A., & Dutton, R. W. (1997). Delaunay Triangulation and 3D Adaptive Mesh Generation. Finite Elements in Analysis and Design, 25(3\u20134), 331\u2013341. doi: 10.1016\/S0168-874X(96 )00054-6 ."},{"key":"9195_CR36","unstructured":"CGAL Editorial Board. (2011). The CGAL Project: CGAL user and reference manual (3.9th ed.). http:\/\/www.cgal.org\/Manual\/3.9\/doc_html\/cgal_manual\/packages.html ."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-012-9195-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10458-012-9195-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-012-9195-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,27]],"date-time":"2019-06-27T12:00:23Z","timestamp":1561636823000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10458-012-9195-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4,21]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9195"],"URL":"https:\/\/doi.org\/10.1007\/s10458-012-9195-8","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,21]]}}}