{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:31:29Z","timestamp":1787326289577,"version":"build-2736575974"},"reference-count":15,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>\n                    D* is a greedy heuristic planning method that is widely used in robotics, including several Nomad class robots and the Mars rover prototype, to reach a destination in unknown terrain. We obtain nearly sharp lower and upper bounds of $\\Omega(n\\log n\/\\log\\log n)$ and O(n log n), respectively, on the worst-case total distance traveled by the robot, for the grid graphs on n vertices typically used in robotics applications. For arbitrary graphs we prove an O(n log\n                    <jats:sup>2<\/jats:sup>\n                    n ) upper bound.\n                  <\/jats:p>","DOI":"10.1137\/s089548010444256x","type":"journal-article","created":{"date-parts":[[2005,11,21]],"date-time":"2005-11-21T21:00:27Z","timestamp":1132606827000},"page":"431-447","source":"Crossref","is-referenced-by-count":5,"title":["Bounds on the Travel Cost of a Mars Rover Prototype Search Heuristic"],"prefix":"10.1137","volume":"19","author":[{"given":"Apurva","family":"Mudgal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Craig","family":"Tovey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sam","family":"Greenberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sven","family":"Koenig","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200002"},{"key":"R2","unstructured":"B. Brumitt and A. Stentz,\n                      GRAMMPS: A generalized mission planner for multiple mobile robots\n                      , in Proceedings of the International Conference on Robotics and Automation, Leuven, Belgium, 1998."},{"key":"R3","unstructured":"M. Hebert, R. McLachlan, and P. Chang,\n                      Experiments with driving modes for urban robots\n                      , in Proceedings of the SPIE Mobile Robots, Boston, 1999."},{"key":"R4","unstructured":"S. Koenig and M. Likhachev,\n                      Improved fast replanning for robot navigation in unknown terrain\n                      , in Proceedings of the International Conference on Robotics and Automation, Washington, D. C., 2002, pp. 968\u2013975."},{"key":"R5","unstructured":"S. Koenig, C. Tovey, and W. Halliburton,\n                      Greedy mapping of terrain\n                      , in Proceedings of the International Conference on Robotics and Automation, Seoul, Korea, 2001, pp. 3594\u20133599."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(03)00062-6"},{"key":"R7","unstructured":"L. Matthies, Y. Xiong, R. Hogg, D. Zhu, A. Rankin, B. Kennedy, M. Hebert, R. Maclachlan, C. Won, T. Frost, G. Sukhatme, M. McHenry, and S. Goldberg,\n                      A portable, autonomous, urban reconnaissance robot\n                      , in Proceedings of the International Conference on Intelligent Autonomous Systems, Paris, France, 2000."},{"key":"R8","unstructured":"I. Nourbakhsh,\n                      Interleaving Planning and Execution for Autonomous Robots\n                      , Kluwer Academic Publishers, Dordrecht, The Netherlands, 1997."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF00162467"},{"key":"R10","unstructured":"Y. Smirnov,\n                      Hybrid Algorithms for On\u2010Line Search and Combinatorial Optimization Problems\n                      , Tech. report CMU\u2010CS\u201097\u2010171, Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, 1997;"},{"key":"R10","unstructured":"available online from http:\/\/www.cs. cmu.edu\/afs\/cs\/cmu.edu\/user\/smir\/www\/home\/html."},{"key":"R11","unstructured":"A. Stentz,\n                      The focused D* algorithm for real\u2010time replanning\n                      , in Proceedings of the International Joint Conference on Artificial Intelligence, Montreal, Quebec, 1995, pp. 1652\u20131659."},{"key":"R12","unstructured":"A. Stentz,\n                      CD*: A real\u2010time resolution optimal re\u2010planner for globally constrained problems\n                      , in Proceedings of the National Conference on Artificial Intelligence, Edmonton, Alberta, 2002, pp. 605\u2013612."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00735431"},{"key":"R14","unstructured":"S. Thayer, B. Digney, M. Diaz, A. Stentz, B. Nabbe, and M. Hebert,\n                      Distributed robotic mapping of extreme environments\n                      , in Proceedings of the SPIE: Mobile Robots XV and Telemanipulator and Telepresence Technologies VII, Vol. 4195, Boston, 2000."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S089548010444256X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:29:24Z","timestamp":1787322564000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S089548010444256X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S089548010444256X"],"URL":"https:\/\/doi.org\/10.1137\/s089548010444256x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}