Abstract
We talk about two key aspects of the quality-time trade-offs in time limited search based reasoning namely, design of efficient anytime algorithms and formulations for meta-reasoning (or control) to optimize the computational trade-off under various constrained environments. We present the ideas behind novel anytime heuristic search algorithms, both contract and interruptible. We also describe new meta-control strategies that address parameter control along with time deliberation.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Boddy, M., Dean, T.: Deliberation scheduling for problem solving in time-constrained environments. Artificial Intelligence 67, 245–285 (1994)
Aine, S.: New Approaches to Design and Control of Anytime Algorithmd. PhD thesis, Indian Institute of Technology Kharagpur, Department of Computer Science and Engineering, IIT Kharagpur 721302 India (2008)
van Laarhoven, P., Aarts, E.: Simulated Annealing: Theory and Applications. Kluwer, Dordrecht (1992)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston (1989)
Pohl, I.: Heuristic search viewed as path finding in a graph. Artif. Intell. 1(3), 193–204 (1970)
Likhachev, M., Gordon, G.J., Thrun, S.: Ara*: Anytime A* with provable bounds on sub-optimality. In: Advances in Neural Information Processing Systems, vol. 16, MIT Press, Cambridge (2004)
Zhang, W.: Complete anytime beam search. In: Proceedings of 14th National Conference of Artificial Intelligence AAAI 1998, pp. 425–430. AAAI Press, Menlo Park (1998)
Zhou, R., Hansen, E.A.: Beam-stack search: Integrating backtracking with beam search. In: Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS 2005), Monterey, CA, pp. 90–98 (2005)
Pearl, J.: Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley Longman Publishing Co., Inc., Boston (1984)
Dean, T., Boddy, M.: An analysis of time-dependent planning. In: Proceedings of 6th National Conference on Artificial Intelligence (AAAI 1988), St. Paul, MN, pp. 49–54. AAAI Press, Menlo Park (1988)
Hansen, E.A., Zilberstein, S.: Monitoring and control of anytime algorithms: A dynamic programming approach. Artificial Intelligence 126(1-2), 139–157 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chakrabarti, P.P., Aine, S. (2009). New Approaches to Design and Control of Time Limited Search Algorithms. In: Chaudhury, S., Mitra, S., Murthy, C.A., Sastry, P.S., Pal, S.K. (eds) Pattern Recognition and Machine Intelligence. PReMI 2009. Lecture Notes in Computer Science, vol 5909. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11164-8_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-11164-8_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11163-1
Online ISBN: 978-3-642-11164-8
eBook Packages: Computer ScienceComputer Science (R0)