Dissertation > Excellent graduate degree dissertation topics show

A Logical Characterization of AI Planning

Author: SunZuo
Tutor: CaiZiXing
School: Central South University
Course: Computer Science and Technology
Keywords: AI Planning Computational Complexity DescriptiveComplexity PDDL Mathematical Logic
CLC: TP18
Type: Master's thesis
Year: 2013
Downloads: 6
Quote: 0
Read: Download Dissertation

Abstract


Abstract:Classic Planning has been one of the most important research topics in AI. However the complexity of solving planning problem has encumbered its application in real-life. As a result, analytical study delving into the complexity issue of planning has been a popular topic among researchers. We try to study the complexity of planning from a logic perspective. In this thesis we propose a novel approach, to describe planning with formal logic language, and furthermore we provide the corresponding algorithm to translate it into traditional action-based planning description. Up to our knowledge, before us, there is no existing method that is able to interpret general-descried PSPACE problem as action-based planning formalisms.Our approach is based on Second-order Logic with Transitive Closure (SO(TC)). To begin with, we propose a normal form for SO(TC) and prove its completeness, thereby obtaining a normalization algorithm for all formulae under its realm. In addition, we propose a reduction that directly translates this normal form into a planning problem to complete our approach. The resulting language encrypts a "domain+problem" combination using the versatile planning description language——PDDL. The value of our approach can be reflected in a few facets. On one hand, this method allows us to use planning technique to solve logic model checking problem which are either hand-coded or obtained by translating from other formal descriptions. On the other hand, the formal logic we use here can be seen as a compact and unified description of planning which we believe would be beneficial for analytical study.This algorithm is implemented with C++programming language, is able to generate PDDL-code that can be directly fed into planning problem solvers. In addition to that, we prove some important theoretical properties of our algorithm. One of which testifies that our approach, while translating problems into a PSPACE framework, is able to preserve the complexity class NP.

Related Dissertations

  1. The Research and Implementation of Service Domain-based Automatic Service Composition,TP393.09
  2. The Batch Scheduling Problems in Supply Chain Management,O223
  3. Philosophical Perspective Mathematical crisis,N02
  4. Research on PDDL-Based Imaging Satellite Operation Planning Problem,V556
  5. Analysis of the Erik Satie’s Sarabandes,J624.1
  6. Research on Optical Wavelet Transform System,TN929.1
  7. An Multi-Agent Based Approach for Automated Semantic Web Services Composition,TP393.092
  8. The Research on Path-following Algorithms for a Class of Complementary Problem,O224
  9. Study on Adequacy Equivalent Model for Bulk Power System,TM743
  10. Study on Approximation Algorithms for Some Class of Geometry Optimization Problem,O224
  11. The Study of Quick MD5 Collision Algorithms,TN918.1
  12. Quasi-Physical Quasi-Human Algorithm for Protein Folding,TP301.6
  13. Adaptive Allocation Algorithms and Their Computational Complexity in OFDM System,TN919.3
  14. Some Problems with noise speech coding,TN912.3
  15. Combinatorial Optimization Problems with Reverse Objective,O224
  16. The Formal Analysis Methods of Wireless Network Security Protocol,TP393.08
  17. Sequence in the Rhythm and Mathematical Logic of Music Audition,J613.7
  18. Reserch on Distributed Location Algorithm of Wireless Sensor Network,TP212.9
  19. Machine Scheduling Problems with Subcontracting Options,O223
  20. Algorithms for Abitrary Roots of Circulant Matrices,O151.21

CLC: > Industrial Technology > Automation technology,computer technology > Automated basic theory > Artificial intelligence theory
© 2012 www.DissertationTopic.Net  Mobile