Paper Info
Title
The classical AI planning problems in the mirror of Horn linear logic: semantics, expressibility, complexity
Abstract
We introduce Horn linear logic as a comprehensive logical system capable of handling the typical AI problem of making a plan of the actions to be performed by a robot so that he could get into a set of final situations, if he started with a certain initial situation. Contrary to undecidability of propositional Horn linear logic, the planning problem is proved to be decidable for a reasonably wide class of natural robot systems.The planning problem is proved to be EXPTIME-complete for the robot systems that allow actions with non-deterministic effects. Fixing a finite signature, that is a finite set of predicates and their finite domains, we get a polynomial time procedure of making plans for the robot system over this signature.The planning complexity is reduced to PSPACE for the robot systems with only pure deterministic actions.As honest numerical parameters in our algorithms we invoke the length of description of a planning task ‘from W to Z˜’ and the Kolmogorov descriptive complexity of Ax T, a set of possible actions.
Year
DOI
Venue
2001
10.1017/S0960129501003413
Mathematical Structures in Computer Science
Keywords
Field
DocType
linear logic,ai planning
Discrete mathematics,Finite set,EXPTIME,Decidability,Descriptive complexity theory,PSPACE,Linear logic,Time complexity,Mathematics,Computational complexity theory
Journal
Volume
Issue
Citations 
11
6
17
PageRank 
References 
Authors
0.65
11
2
Name
Order
Citations
PageRank
Max I. Kanovich123630.66
Jacqueline Vauzeilles28111.63