Automated Planning: Theory and Practice

ISBN-13: 9781558608566 / Angielski / Twarda / 2004 / 635 str.

Dana Nau; Malik Ghallab; Paolo Traverso

Opis

Automated planning technology now plays a significant role in a variety of demanding applications, ranging from controlling space vehicles and robots to playing the game of bridge. These real-world applications create new opportunities for synergy between theory and practice: observing what works well in practice leads to better theories of planning, and better theories lead to better performance of practical applications. Automated Planning mirrors this dialogue by offering a comprehensive, up-to-date resource on both the theory and practice of automated planning. The book goes well beyond classical planning, to include temporal planning, resource scheduling, planning under uncertainty, and modern techniques for plan generation, such as task decomposition, propositional satisfiability, constraint satisfaction, and model checking. The authors combine over 30 years experience in planning research and development to offer an invaluable text to researchers, professionals, and graduate students.

• Provides a thorough understanding of AI planning theory and practice, and how they relate to each other
• Covers all the contemporary topics of planning, as well as important practical applications of planning, such as model checking and game playing
• Presents case studies and applications in planning engineering, space, robotics, CAD/CAM, process control, emergency operations, and games
• Provides lecture notes, examples of programming assignments, pointers to downloadable planning systems and related information online

Recenzje

"Automated Planning is a tremendous book! It provides an extremely comprehensive, systematic, and clear coverage of this important and exciting field of AI. Readers will not only gain a deep understanding of the theoretical foundations of planning; they will actually learn how this future-oriented technology is to be applied in a variety of areas. Automated Planning is just the standard AI planning textbook we have been waiting for." --Professor Susanne Biundo, Director of PLANET, the European Network of Excellence in AI Planning

"This book is an excellent resource for both students and teachers, and a valuable reference guide for seasoned planning researchers. It covers a surprising level of technical details for its size, yet is quite accessible to t the mathematically astute reader. I would like to thank the authors for making this body of knowledge accessible to a wider audience." --Kutluhan Erol, Mindlore, Inc.

Planning research, which has been a key area in AI since the General Problem Solver of Newell and Simon in 50's, has undergone significant progress in the last few years. In this book, Malik Ghallab, Dana Nau, and Paolo Traverso, three leading AI planning researchers, provide the first balanced and comprehensive introduction to this exciting and fast moving field. --Hector Geffner, Universitat Pompeu Fabra

"AI planning experts, teachers, and students have been waiting for ages for the first textbook about the field---the comprehensive, up-to-date synthesis. Here it is! An admirable piece of work that will undoubtedly become a standard reference." --Joachim Hertzberg, Fraunhofer Institute for Autonomous Intelligent Systems

"A much needed and timely compendium that conveys both the diverse history and the current excitement of the research in Automated Planning." --Subbarao Kambhampati, Arizona State University

"The publication of this book creates an opportunity for planning to reach a much wider community than specialized researchers, to capture the imaginations of a new generation of AI students, both graduates and undergraduates, showing that while planning is rooted in strong theoretical foundations, its applications can reach from intelligent game play to evacuation operations and even to the stars! I am certain that it will find a place on the bookshelves of every serious planning researcher, but its true place is in the minds of our undergraduate and graduate students whom it should inspire to add to the impressive body of work it describes." --Derek Long, University of Strathclyde

"In recent years, comprehensive texts have been written for several of the other major areas of Artificial Intelligence, including machine learning, natural-language processing, and constraint-satisfaction processing, but until now, the field of planning has been devoid of such a resource, despite the considerable number of advances in and the significant maturation of planning research in the past decade. With Automated Planning: Theory and Practice, Malik Ghallab, Dana Nau, and Paolo Traverso have filled that void, and have done so with a remarkably clear and well-written book." --Martha Pollack, University of Michigan

"The authors cover a vast range of topics in planning research. The reader will find methodical formalisms of theoretical concepts with illustrative examples, as well as practical case studies. Well-developed exercises provide practice for students of planning. This is a great book." --Stephen Smith, Great Game Products "The engineer who needs to know how to use AI planning is on his own, in the tangled forest of undigested reports of original research.Until now, that is. For the first time there is a text that is comprehensive, structured and up to date. Automated Planning provides both the graduate student of AI and the engineer faced with designing an autonomous system with the reference they really need." --Sam Steele, University of Essex

"Planning is one of the most important aspects of intelligent behavior. AI techniques to automate it are a significant challenge. This textbook guides you through the advances made in 40 years of pioneering R&D. It provides a uniform theoretical framework as a basis for showing how practical planners are developed. Based on the authors' wide experience in teaching and tutorials, the book provides a range of learning paths adaptable to the reader's needs." --Austin Tate, AIAI, University of Edinburgh

"By synthesizing a broad range of planning approaches into a common conceptual framework and explaining them with a common set of problems, this book provides unique clarity in understanding these approaches and their interrelationships." --David Wilkins, SRI International

Spis treści

1 Introduction and Overview

I Classical Planning 2 Representations for Classical Planning3 Complexity of Classical Planning4 State-Space Planning5 Plan-Space Planning II Neoclassical Planning 6 Planning-Graph Techniques7 Propositional Satisfiability Techniques8 Constraint Satisfaction Techniques

III Heuristics and Control Strategies 9 Heuristics in Planning10 Control Rules in Planning11 Hierarchical Task Network Planning12 Control Strategies in Deductive Planning IV Planning with Time and Resources 13 Time for Planning14 Temporal Planning15 Planning and Resource Scheduling

V Planning under Uncertainty 16 Planning based on Markov Decision Processes17 Planning based on Model Checking18 Uncertainty with Neo-Classical Techniques

VI Case Studies and Applications 19 Space Applications20 Planning in Robotics21 Planning for Manufacturability Analysis22 Emergency Evacuation Planning 23 Planning in the Game of Bridge

VII Conclusion 24 Conclusion and Other Topics

VIII Appendices A Search Procedures and Computational ComplexityB First Order LogicC Model Checking

O autorze

Malik Ghallab is Director of Research at the Laboratoire d'Analyse et d'Architecture des Systèmes, Centre National de la Recherche Scientifique, LAAS-CNRS, Toulouse. He was the director of the French national AI program, coordinated the five national research programs in information science, and served as the chair of ASTI, the French technical society in information sciences and technologies. Currently, he is also the director of the French national interdisciplinary program on robotics and artificial entities (Robea). Dana Nau is a professor at the University of Maryland, and an AAAI Fellow. His research interests include AI planning and searching, and computer-integrated design and manufacturing. He holds appointments in the Department of Computer Science, the Institute for Systems Research, the Institute for Advanced Computer Studies, and the Department of Mechanical Engineering. He has more than 250 technical publications, and has co-authored computer programs that won the 1997 world championship of computer bridge and one of the top four awards in the 2002 International Planning Competition. Other awards he has received include an NSF graduate fellowship, an NSF Presidential Young Investigator award, an Outstanding Faculty award, and several "best paper” awards. Paolo Traverso is the Head of Sistemi di Ragionamento Automatico at the Instituto Trentino di Cultura - Instituto per la Ricerca Scientifica e Tecnologica, (ITC-IRST). He was the project leader of industrial and experimental projects such as the development of Rail Traffic Management Systems, the design of tools for Automatic Train Protection, the synthesis of industrial controllers, and the development of systems for planning and control in space environment.