YUNFEI JIANG

IJCAI Conference 2009 Conference Paper

• Wei Huang
• Zhonghua Wen
• YUNFEI JIANG
• Hong Peng

In many real world planning domains, some observation information is optional and useless to the execution of a plan; on the other hand, information acquisition may require some kind of cost. The problem of observation reduction for strong plans has been addressed in the literature. However, observation reduction for plans with contexts (which are more general and useful than strong plans in robotics) is still a open problem. In this paper, we present an attempt to solve the problem. Our first contribution is the definition of structured plans, which can encode sequential, conditional and iterative behaviors, and is expressive enough for dealing with incomplete observation information and internal states of the agent. A second contribution is an observation reduction algorithm for plans with contexts, which can transform a plan with contexts into a structured plan that only branches on necessary observation information.

TIME Conference 2008 Conference Paper

Topology-based Variable Ordering Strategy for Solving Disjunctive Temporal Problems

• Yuechang Liu
• Yunfei Jiang
• Hong Qian

Many temporal problems arising in automated planning and scheduling can be expressed as disjunctive temporal problems (DTPs). Most of DTP solvers in the literature treat DTPs as constraint satisfaction problems (CSPs) or satisfiability problems (SATs), and solve them using standard CSP (SAT) techniques. Basically DTPs are represented through logically related topological relations between temporal variables, however, unfortunately little work has been done on exploiting the topological information to direct the search for DTP resolving. According to the "fail-first "(FF) principle for dynamic variable ordering (DVO) heuristics in CSP literature, this paper proposes a DVO which is based on the topological structure of DTP (which is defined to be Disjunctive Temporal Network). Experimental results reveal that the proposed DVO outperforms Minimal Remaining Values heuristics-a DVO that is widely used in existing DTP solvers, especially for the hard and large-scale problems. And, a CSP based procedure with the best of the heuristics wins TSAT++ on most of the test problems.

IJCAI Conference 2007 Conference Paper

• Zhao-Fu Fan
• YUNFEI JIANG

This paper presents a new modeling approach for IMP programs with operator component matrix(OCM) model, which can be used in IMP program diagnosis. Using this model and model-based diagnosis method, some logic errors can be found in IMP programs. The model can also be extended to all kinds of imperative programs. The advantages of this diagnosis method lie in its simple and regular presentation, uniform diagnosed objects, usage of isomorphism assumptions in structure, and usage of assertions about the expected program. These advantages make diagnoses more accurate, and even help to correct the faults by mutation of operator components.

IJCAI Conference 2007 Conference Paper

• Wei Huang
• Zhonghua Wen
• YUNFEI JIANG
• Lihua Wu

Strong planning under full or partial observability has been addressed in the literature. But this research line is carried out under the hypothesis that the set of observation variables is fixed and compulsory. In most real world domains, however, observation variables are optional and many of them are useless in the execution of a plan; on the other side, information acquisition may require some kind of cost. So it is significant to find a minimal set of observation variables which are necessary for the execution of a plan, and to best of our knowledge, it is still an open problem. In this paper we present a first attempt to solve the problem, namely, we define an algorithm that finds an approximate minimal set of observation variables which are necessary for the execution of a strong plan under full observability (i. e. a state-action table); and transforms the plan into a strong plan under partial observability (i. e. a conditional plan branching on the observations built on these observation variables).

KER Journal 2007 Journal Article

ARMS: an automatic knowledge engineering tool for learning action models for AI planning

• KANGHENG WU
• Qiang Yang
• YUNFEI JIANG

Abstract We present an action model learning system known as ARMS (Action-Relation Modelling System) for automatically discovering action models from a set of successfully observed plans. Current artificial intelligence (AI) planners show impressive performance in many real world and artificial domains, but they all require the definition of an action model. ARMS is aimed at automatically learning action models from observed example plans, where each example plan is a sequence of action traces. These action models can then be used by the human editors to refine. The expectation is that this system will lessen the burden of the human editors in designing action models from scratch. In this paper, we describe the ARMS in detail. To learn action models, ARMS gathers knowledge on the statistical distribution of frequent sets of actions in the example plans. It then builds a weighted propositional satisfiability (weighted SAT) problem and solves it using a weighted MAXSAT solver. Furthermore, we show empirical evidence that ARMS can indeed learn a good approximation of the finally action models effectively.

TIME Conference 2007 Conference Paper

Graph-DTP: Graph-Based Algorithm for Solving Disjunctive Temporal Problems

• Yuechang Liu
• Hong Qian
• Yunfei Jiang

We study an expressive quantitative temporal model: disjunctive temporal problem (DTP), which was first proposed only in 1998 (Stergiou and Koubarakis). As extension of temporal constraint satisfaction problem (TCSP) (Dechter et al. 1991), DTP differs from TCSP in that two disjuncts in a same disjunctive constraint do not necessarily refer to same temporal variables. Traditionally, most of the DTP algorithms in the literature solve DTPs by treating them as constraint satisfaction problems (CSPs), and searching for solutions using standard CSP techniques, e. g. backtracking, back-jumping, forward checking, semantic branching, removal of subsumed variables, nogood recording, etc. Those CSP techniques are powerful in solving DTPs. However, an evident drawback of viewing DTPs as general CSPs is that much semantic information encoded in DTPs is neglected. In fact we can mine rich semantic information that can be exploited to reduce search space for DTPs (more than semantic branching). Through some topological analysis on the graphical representation of the problems, some techniques are developed to help to search solutions for other temporal models (e. g. TCSP), or to identify "crucial subproblems" for CSP (Epstein and Wallace, 2006). However, little effort has been made to exploit the inherent topological information in solving DTPs. Our idea runs on a graphical representation of DTPs - disjunctive temporal network (DTN). We define DTN as an edge-labeled weighted digraph, on which some relevant concepts are identified. Then, we define the concept of equivalency between DTNs with respect to their consistency. For a given DTN, deciding its consistency is ascribed to check the consistency of a DTN which is equivalent to it and has less constraints (edges). We iteratively reduce a DTN to a simpler but equivalent one according to a set of designed reduction rules (which can be performed within polynomial time). It is hoped that when the DTN reaches a fixed point under such reduction operation, the resulted DTN has minimal edges (which is like backdoor in SAT, or "near clique"). At last the resulted DTN (DTP) is transferred to CSP search phase, where we derive a special variable ordering strategy again through the DTN structure. We shall describe the generation of DTN structure, the DTN reduction rules, the implementation of the complete graph-DTP algorithm, and some first results of this approach.

AIJ Journal 2007 Journal Article

Learning action models from plan examples using weighted MAX-SAT

• Qiang Yang
• KANGHENG WU
• YUNFEI JIANG

AI planning requires the definition of action models using a formal action and plan description language, such as the standard Planning Domain Definition Language (PDDL), as input. However, building action models from scratch is a difficult and time-consuming task, even for experts. In this paper, we develop an algorithm called ARMS (action-relation modelling system) for automatically discovering action models from a set of successful observed plans. Unlike the previous work in action-model learning, we do not assume complete knowledge of states in the middle of observed plans. In fact, our approach works when no or partial intermediate states are given. These example plans are obtained by an observation agent who does not know the logical encoding of the actions and the full state information between the actions. In a real world application, the cost is prohibitively high in labelling the training examples by manually annotating every state in a plan example from snapshots of an environment. To learn action models, ARMS gathers knowledge on the statistical distribution of frequent sets of actions in the example plans. It then builds a weighted propositional satisfiability (weighted MAX-SAT) problem and solves it using a MAX-SAT solver. We lay the theoretical foundations of the learning problem and evaluate the effectiveness of ARMS empirically.

ICAPS Conference 2005 Conference Paper

Learning Actions Models from Plan Examples with Incomplete Knowledge

• Qiang Yang 0001
• Kangheng Wu
• Yunfei Jiang

AI planning requires the definition of an action model using a language such as PDDL as input. However, building an action model from scratch is a difficult and time-consuming task even for experts. In this paper, we develop an algorithm called ARMS for automatically discovering action models from a set of successful plan examples. Unlike the previous work in action-model learning, we do not assume complete knowledge of states in the middle of the example plans; that is, we assume that no intermediate states are given. This requirement is motivated by a variety of applications, including object tracking and plan monitoring where the knowledge about intermediate states is either minimal or unavailable to the observing agent. In a real world application, the cost is prohibitively high in labelling the training examples by manually annotating every state in a plan example from snapshots of an environment. To learn action models, our ARMS algorithm gathers knowledge on the statistical distribution of frequent sets of actions in the example plans. It then builds a propositional satisfiability (SAT) problem and solves it using a SAT solver. We lay the theoretical foundations of the learning problem and evaluate the effectiveness of ARMS empirically