DEMONSTRATION‐BASED BEHAVIOR PROGRAMMING FOR EMBODIED VIRTUAL AGENTS

We present a novel technique for behavioral animation through data‐driven behavior synthesis. This technique has two key features: it provides natural character behavior and has a programming‐by‐demonstration interface. Thus we can quickly create compelling autonomous virtual agents that exhibit stylized behavior. First, the human user demonstrates behavior for the character by specifying its high‐level actions (e.g., with a joystick) during an interactive session. Each demonstration is recorded as a sequence of discrete actions. Later, the character synthesizes novel behavior by concatenating segments of action sequences. The choice of segments is guided by simulations that predict fitness. Thus our technique operates such as a cognitive model, providing a character with deliberative decision making. The actions are abstract and can be mapped to any pertinent motions, even procedurally synthesized motions. Thus our technique complements character animation algorithms. We empirically show that our O(log n) technique is scalable, robust when provided with sufficient data, produces effective behavior for a number of problem domains, and is faster than traditional planning. Also, the interface is intuitive enough that character behavior can be created by nontechnical users.     

LEARNING AND VERIFYING SAFETY CONSTRAINTS FOR PLANNERS IN A KNOWLEDGE‐IMPOVERISHED SYSTEM

We present a Bayesian approach to learning flexible safety constraints and subsequently verifying whether plans satisfy these constraints. Our approach, called the Safety Constraint Learner/Checker (SCLC), infers safety constraints from a single expert demonstration trace and minimal background knowledge, and applies these constraints to the solutions proposed by multiple planning agents in an integrated and heterogeneous ensemble. The SCLC calculates how much to blame plan fragments (partial solutions) generated by the individual planning agents. This information is used when composing these fragments into a final overall plan. In particular, fragments whose safety violations exceed a threshold are rejected. This facilitates the generation of safe plans. We have integrated the SCLC within the Generalized Integrated Learning Architecture, which was designed for Defense Advanced Research Projects Agency (DARPA)’s Integrated Learning (IL) program. The main goal of the IL program is to promote the development and success of sophisticated systems that learn to solve challenging real‐world problems based on a simple demonstration by a human expert and exiguous domain knowledge. We present experimental results showing the advantages of the SCLC on two multiagent problem‐solving tasks that were benchmark applications in DARPA’s IL program.     

A NEW DESIGN APPROACH TO DELAY‐DEPENDENT ROBUST H∞ CONTROL FOR UNCERTAIN TIME‐DELAY SYSTEMS

A new design approach to delay‐dependent robust stabilization and robust H∞ control for a class of uncertain time‐delay systems is provided in this paper. The sufficient conditions for delay‐dependent robust stabilization and robust H∞ control are derived based on a new state transformation and given in terms of linear matrix inequalities (LMI). Numerical examples are presented to show that the proposed results can be less conservative and can be used to deal with not only small but also large delay systems.     

SOLVING ABSTRACT COOPERATIVE PATH‐FINDING IN DENSELY POPULATED ENVIRONMENTS

The problem of cooperative path‐finding is addressed in this work. A set of agents moving in a certain environment is given. Each agent needs to reach a given goal location. The task is to find spatial temporal paths for agents such that they eventually reach their goals by following these paths without colliding with each other. An abstraction where the environment is modeled as an undirected graph is adopted—vertices represent locations and edges represent passable regions. Agents are modeled as elements placed in the vertices while at most one agent can be located in a vertex at a time. At least one vertex remains unoccupied to allow agents to move. An agent can move into unoccupied neighboring vertex or into a vertex being currently vacated if a certain additional condition is satisfied. Two novel scalable algorithms for solving cooperative path‐finding in bi‐connected graphs are presented. Both algorithms target environments that are densely populated by agents. A theoretical and experimental evaluation shows that the suggested algorithms represent a viable alternative to search based techniques as well as to techniques employing permutation groups on the studied class of the problem.     

EXPLOITING SUBTREES IN AUTO‐PARSED DATA TO IMPROVE DEPENDENCY PARSING

Dependency parsing has attracted considerable interest from researchers and developers in natural language processing. However, to obtain a high‐accuracy dependency parser, supervised techniques require a large volume of hand‐annotated data, which are extremely expensive. This paper presents a simple and effective approach for improving dependency parsing with subtrees derived from unannotated data, which are easy to obtain. First, we use a baseline parser to parse large‐scale unannotated data. Then, we extract subtrees from dependency parse trees in the auto‐parsed data. Next, the extracted subtrees are classified into several sets according to their frequency. Finally, we design new features based on the subtree sets for parsing algorithms. To demonstrate the effectiveness of our proposed approach, we conduct experiments on the English Penn Treebank and Chinese Penn Treebank. The results show that our approach significantly outperforms baseline systems. It also achieves the best accuracy for the Chinese data and an accuracy competitive with the best known systems for the English data.