Institute for Systems Research
Permanent URI for this communityhttp://hdl.handle.net/1903/4375
Browse
Search Results
Item Language, Behaviors, Hybrid Architectures and Motion Control(1997) Manikonda, Vikram; Krishnaprasad, Perinkulam S.; Hendler, James A.; ISRIn this paper we put forward a framework that integrates features of reactive planning models with modern control-theory-based approaches to motion control of robots. We introduce a motion description language, MDLe, that provides a formal basis for robot programming using behaviors, and at the same time permits incorporation of kinematic and dynamic models of robots given in the form of differential equations. In particular, behaviors for robots are formalized in terms of kinetic state machines, a motion description language, and the interaction of the kinetic state machine with real-time information from (limited range) sensors. This formalization allows us to create a mathematical basis for the study of such systems, including techniques for integrating sets of behaviors. In addition we suggest optimality criteria for comparing both atomic and compound behaviors in various environments. We demonstrate the use of MDLe in the area of motion planning for nonholonomic robots. Such models impose limitations on the stabilizability via smooth feedback; piecing together open loop and closed loop trajectories becomes essential in these circumstances, and MDLe enables one to describe such piecing together in a systematic manner. A reactive planner using the formalism of the paper is described. We demonstrate obstacle avoidance with limited range sensors as a test of this planner.Item A Planning Approach to Declarer Play in Contract Bridge(1995) Smith, S.J.J.; Nau, D.S.; Throop, T.A.; ISRAlthough game-tree search works well in perfect-information games, it is less suitable for imperfect-information games such as contract bridge. The lack of knowledge about the opponents' possible moves gives the game tree a very large branching factor, making it impossible to search a significant portion of this tree in a reasonable amount of time.This paper describes our approach for overcoming this problem. We represent information about bridge in a task network that is extended to represent multi-agency and uncertainty. Our game-playing procedure uses this task network to generate game trees in which the set of alternative choices is determined not by the set of possible actions, but by the set of available tactical and strategic schemes.
We have tested this approach on declarer play in the game of bridge, in an implementation called Tignum 2. On 5,000 randomly generated no-trump deals, Tignum 2 beat the strongest commercially available program by 1394 to 1302, with 2304 ties. These results are statistically significant at the a = 0.05 level. Tignum 2 searched an average of only 8745.6 moves per deal in an average time of only 27.5 seconds per deal on a Sun SPARCstation 10. Further enhancements to Tignum 2 are currently underway.
Item A Critical Look at Critics in HTN Planning(1995) Erol, Kutluhan; Hendler, James A.; Nau, D.S.; Tsuneto, R.; ISRDetecting interactions and resolving conflicts in one of the key issues for generative planning systems. Hierarchical Task Network (HTN) planning systems use critics for this purpose. Critics have provided extra efficiency and flexibility to HTN planning systems, but their procedural -- and sometimes domain- specific - - nature has not been amenable to analytical studies. As a result, little work is available on the correctness or efficiency of critics. This paper describes a principled approach to handling conflicts, as implemented in UMCP, an HTN planning system. Critics in UMCP have desirable properties such as systematicity, and the preservation of soundness and completeness.Item Complexity Results for HTN Planning(1995) Erol, Kutluhan; Hendler, James A.; Nau, D.S.; ISRMost practical work on AI planning systems during the last fifteen years has been based on hierarchical task network (HTN) decomposition, but until now, there has been very little analytical work on the properties of HTN planners. This paper describes how the complexity of HTN planning varies with various conditions on the task networks, and how it compares to STRIPS- style planning.Item Semantics for Hierarchical Task-Network Planning(1995) Erol, Kutluhan; Hendler, James A.; Nau, Dana S.; ISROne big obstacle to understanding the nature of hierarchical task network (HTN) planning has been the lack of a clear theoretical framework. In particular, no one has yet presented a clear and concise HTN algorithm that is sound and complete. In this paper, we present a formal syntax and semantics for HTN planning. Based on this syntax and semantics, we are able to define an algorithm for HTN planning and prove it sound and complete. We also develop several definitions of expressivity for planning languages and prove that HTN planning is strictly more expressive than STRIPS- style planning according to those definitions.Item Complexity of Production Management in a Petri Net Environment(1994) Proth, J-M.; Minis, Ioannis; ISRThe objective of this paper is to show that Petri nets facilitate a comprehensive approach to production management and reduce the complexity of the problems involved at the expense of some constraints imposed on the decision making systems.The first part of the paper focuses on cyclic manufacturing systems. For this type of systems, it is always possible to propose an event graph model which represents both the physical and the decision making systems. We use such a model to propose a near-optimal scheduling algorithm that maximizes productivity while minimizing the work-in-process (WIP) in the deterministic case.
The approach used for non-cyclic manufacturing systems is different in the sense that only the manufacturing processes (i.e. the physical part of the system) and the related constraints are modeled using Petri nets. We use such a Petri net model to propose a short-term planning process which results in a trade- off between the computation burden the level of resource utilization. the short-term planning models is then enhanced to obtain the scheduling model. The latter is used to develop an efficient scheduling algorithm that is able to satisfy the requirements imposed by short-term planning.
Item On the Nature of Modal Truth in Plans(1993) Nau, D.S.; ISRChapman's paper, "Planning for Conjunctive Goals", has been widely acknowledged as a major step towards understanding the nature of nonlinear planning, and it has been one of the bases of later work by others -- but it is not free of problems. This paper discusses the following problems with modal truth and the modal truth criterion.1. It is NP-hard to tell, given a plan P and a ground atom p, whether P is possibly true in P's final situation. This is true despite the fact that modal truth criterion can be computed in a polynomial time.
2. The reason for this discrepancy is that the "possible truth" version of the modal truth criterion is incorrect. It tells whether - p is not necessarily true --- but this is different from telling whether p is possibly true. Possible truth is not the dual of necessary truth, as Chapman had thought it was.
3. Instead, possible truth is the dual of another problem, which is co-NP-hard: the problem of determining whether p is true over all executable completions of a plan.
Despite the above problems, the "necessary truth" version of the modal truth criterion (and hence the TWEAK planner) are still correct.
Item Supervenience in Dynamic-World Planning(1992) Spector, L.; Hendler, J.; ISRThis report investigates the utility of abstraction for agents living in complex, dynamic environments. The generation of intelligent behavior in such environments requires the integration of deliberative and reactive processes. Modularity and hierarchy have proven to be valuable organizational principles in this context, and the notion of "levels of abstraction" has played a particularly important role. This report presents a form of abstraction called supervenience, of which other common forms of abstraction are special cases. Supervenience is based on epistemological "distance from the world," and is particularly useful for integrating deliberative processes with actions in a changing environment. Supervenience is discussed in relation to the literature of AI planning systems, the literature of cognitive psychology, and the philosophical literature in which the term originated. Supervenience is described in the context of nonmonotonic reasoning systems, and is compared to related formal constructs. A program based on the concept of supervenience is described, and its performance in a dynamic-world planning domain is demonstrated. This report is a reformatted version of the author's doctoral dissertation.