Anytime search in dynamic graphs

Hart, 1968, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems, Science, and Cybernetics SSC, 4, 100, 10.1109/TSSC.1968.300136 Dijkstra, 1959, A note on two problems in connexion with graphs, Numerische Mathematik, 1, 269, 10.1007/BF01386390 Dechter, 1985, Generalized best-first search strategies and the optimality af A∗, Journal of the Association for Computing Machinery, 32, 505, 10.1145/3828.3830 Zilberstein, 1995, Approximate reasoning using anytime algorithms T.L. Dean, M. Boddy, An analysis of time-dependent planning, in: Proceedings of the National Conference on Artificial Intelligence (AAAI), 1988 H. Moravec, Certainty grids for mobile robots, in: Proceedings of the NASA/JPL Space Telerobotics Workshop, 1987 S. Koenig, Y. Smirnov, Sensor-based planning with the freespace assumption, in: Proceedings of the International Conference on Robotics and Automation (ICRA), 1997 J. Ambite, C. Knoblock, Planning by rewriting: Efficiently generating high-quality plans, in: Proceedings of the National Conference on Artificial Intelligence (AAAI), 1997 S. Zilberstein, S. Russell, Anytime sensing, planning and action: A practical model for robot control, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1993, pp. 1402–1407 N. Hawes, An anytime planning agent for computer game worlds, in: Proceedings of the Workshop on Agents in Computer Games at the 3rd International Conference on Computers and Games (CG'02), 2002 Pai, 1998, Multiresolution rough terrain motion planning, IEEE Transactions on Robotics and Automation, 14, 19, 10.1109/70.660835 H. Prendinger, M. Ishizuka, APS, a prolog-based anytime planning system, in: Proceedings 11th International Conference on Applications of Prolog (INAP), 1998 Korf, 1990, Real-time heuristic search, Artificial Intelligence, 42, 189, 10.1016/0004-3702(90)90054-4 Dasgupta, 1994, Agent searching in a tree and the optimality of iterative deepening, Artificial Intelligence, 71, 195, 10.1016/0004-3702(94)90066-3 S. Koenig, Chapter 2 of goal-directed acting with incomplete information: Acting with agent-centered search, Ph.D. thesis, Carnegie Mellon University, 1997 R. Zhou, E.A. Hansen, Multiple sequence alignment using A∗, in: Proceedings of the National Conference on Artificial Intelligence (AAAI), 2002, Student abstract Hansen, 2007, Anytime heuristic search, Journal of Artificial Intelligence Research (JAIR), 28, 267, 10.1613/jair.2096 J.G. Gaschnig, Performance measurement and analysis of certain search algorithms, Ph.D. thesis, Carnegie Mellon University, 1979 Bonet, 2001, Planning as heuristic search, Artificial Intelligence, 129, 5, 10.1016/S0004-3702(01)00108-4 Korf, 1993, Linear-space best-first search, Artificial Intelligence, 62, 41, 10.1016/0004-3702(93)90045-D Rabin, 2000, A∗ speed optimizations, 272 S. Edelkamp, Planning with pattern databases, in: Proceedings of the European Conference on Planning (ECP), 2001 Bagchi, 1985, Weighted heuristic search in networks, Journal of Algorithms, 6, 550, 10.1016/0196-6774(85)90032-X Chakrabarti, 1988, Admissibility of AO∗ when heuristics overestimate, Artificial Intelligence, 34, 97, 10.1016/0004-3702(87)90005-1 Davis, 1988, The advantages of using depth and breadth components in heuristic search, 19 R. Zhou, E.A. Hansen, Beam-stack search: Integrating backtracking with beam search, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2005, pp. 90–98 D. Furcy, Chapter 5 of speeding up the convergence of online heuristic search and scaling up offline heuristic search, Ph.D. thesis, Georgia Institute of Technology, 2004 W. Zhang, Complete anytime beam search, in: Proceedings of the National Conference on Artificial Intelligence (AAAI), 1998, pp. 425–430 Kumar, 1992, Branch-and-bound search, 1468 R. Simmons, A theory of debugging plans and interpretations, in: Proceedings of the National Conference on Artificial Intelligence (AAAI), 1988, pp. 94–99 A. Gerevini, I. Serina, Fast plan adaptation through planning graphs: Local and systematic search techniques, in: Proceedings of the International Conference on Artificial Intelligence Planning and Scheduling (AIPS), 2000, pp. 112–121 Koehler, 1994, Flexible plan reuse in a formal framework, 171 Veloso, 1994 Alterman, 1988, Adaptive planning, Cognitive Science, 12, 393, 10.1207/s15516709cog1203_3 Kambhampati, 1992, A validation-structure-based theory of plan modification and reuse, Artificial Intelligence, 55, 193, 10.1016/0004-3702(92)90056-4 Hanks, 1995, A domain-independent algorithm for plan adaptation, Journal of Artificial Intelligence Research, 2, 319, 10.1613/jair.79 S. Edelkamp, Updating shortest paths, in: Proceedings of the European Conference on Artificial Intelligence, 1998 K. Trovato, Differential A∗: An adaptive search method illustrated with robot path planning for moving obstacles and goals, and an uncertain environment, Journal of Pattern Recognition and Artificial Intelligence 4 (2) Podsedkowski, 2001, A new solution for path planning in partially known or unknown environment for nonholonomic mobile robots, Robotics and Autonomous Systems, 34, 145, 10.1016/S0921-8890(00)00118-4 A. Stentz, The focussed D∗ algorithm for real-time replanning, in: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1995 Koenig, 2002, Incremental A∗ Ausiello, 1991, Incremental algorithms for minimal length paths, Journal of Algorithms, 12, 615, 10.1016/0196-6774(91)90036-X Even, 1985, Updating distances in dynamic graphs, Methods of Operations Research, 49, 371 D. Frigioni, A. Marchetti-Spaccamela, U. Nanni, Fully dynamic output bounded single source shortest path problem, in: Proceedings of the Symposium on Discrete Algorithms, 1996 Goto, 1978, A new shortest path updating algorithm, Networks, 8, 341, 10.1002/net.3230080406 Lin, 1990, On the dynamic shortest path problem, Journal of Information Processing, 13, 470 Ramalingam, 1996, An incremental algorithm for a generalization of the shortest-path problem, Journal of Algorithms, 21, 267, 10.1006/jagm.1996.0046 H. Rohnert, A dynamization of the all pairs least cost path problem, in: Proceedings of the Symposium on Theoretical Aspects of Computer Science, 1985, pp. 279–286 Ahuja, 2003, Dynamic shortest paths minimizing travel times and costs, Networks, 41, 197, 10.1002/net.10072 Frigioni, 2003, Fully dynamic shortest paths in digraphs with arbitrary arc weights, Journal of Algorithms, 49, 86, 10.1016/S0196-6774(03)00082-8 S. Chien, R. Knight, A. Stechert, R. Sherwood, G. Rabideau, Using iterative repair to improve the responsiveness of planning and scheduling, in: Proceedings of the International Conference on Artificial Intelligence Planning and Scheduling (AIPS), 2000 G.J. Ferrer, Anytime replanning using local subplan replacement, Ph.D. thesis, University of Virginia, 2002 Pearl, 1984 Pohl, 1970, First results on the effect of error in heuristic search, Machine Intelligence, 5, 219 M. Likhachev, Search-based planning for large dynamic environments, Ph.D. thesis, Carnegie Mellon University, 2005 M. Likhachev, S. Koenig, A generalized framework for Lifelong Planning A∗, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2005, pp. 99–108 S. Koenig, M. Likhachev, D∗ lite, in: Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI), 2002 M. Likhachev, G. Gordon, S. Thrun, ARA∗: Formal analysis, Tech. Rep. CMU-CS-03-148, Carnegie Mellon University, Pittsburgh, PA, 2003 M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, S. Thrun, Anytime Dynamic A∗: An anytime, replanning algorithm, in: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2005, pp. 262–271 M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, S. Thrun, Anytime dynamic A∗: The proofs, Tech. Rep. CMU-RI-TR-05-12, Carnegie Mellon University, Pittsburgh, PA, 2005 D. Haehnel, Personal communication, 2003 Culberson, 1998, Pattern databases, Computational Intelligence, 14, 318, 10.1111/0824-7935.00065 S. Koenig, R. Simmons, Easy and hard testbeds for real-time search algorithms, in: Proceedings of the National Conference on Artificial Intelligence (AAAI), 1996 Korf, 1985, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence, 27, 97, 10.1016/0004-3702(85)90084-0 R.E. Korf, W. Zhang, Divide-and-conquer frontier search applied to optimal sequence alignment, in: Proceedings of the National Conference on Artificial Intelligence (AAAI), 2000, pp. 910–916 R. Zhou, E.A. Hansen, Sweep A∗: Space-efficient heuristic search in partially ordered graphs, in: Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2003, p. 427 D. Ferguson, A. Stentz, The delayed D∗ algorithm for efficient path replanning, in: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2005 D. Ferguson, M. Likhachev, A. Stentz, A guide to heuristic-based path planning, in: Proceedings of the Workshop on Planning under Uncertainty for Autonomous Systems at the International Conference on Automated Planning and Scheduling (ICAPS), 2005