Goto

Collaborating Authors

 Country


Motion Planning Algorithms for Autonomous Intersection Management

AAAI Conferences

The impressive results of the 2007 DARPA Urban Challenge showed that fully autonomous vehicles are technologically feasible with current intelligent vehicle hardware. It is natural to ask how current transportation infrastructure can be improved when most vehicles are driven autonomously in the future. Dresner and Stone proposed a new intersection control mechanism called Autonomous Intersection Management (AIM) and showed in simulation that intersection control can be made more efficient than the traditional control mechanisms such as traffic signals and stop signs. In this paper, we extend the study by examining the relationship between the precision of cars' motion controllers and the efficiency of the intersection controller. We propose a planning-based motion controller that can reduce the chance that autonomous vehicles stop before intersections, and show that this controller can increase the efficiency of the intersection control mechanism.


Opponent Behaviour Recognition for Real-Time Strategy Games

AAAI Conferences

In Real-Time Strategy (RTS) video games, players (controlled by humans or computers) build structures and recruit armies, fight for space and resources in order to control strategic points, destroy the opposing force and ultimately win the game. Players need to predict where and how the opponents will strike in order to best defend themselves. Conversely, assessing how the opponents will defend themselves is crucial to mounting a successful attack while exploiting the vulnerabilities in the opponent's defence strategy. In this context, to be truly adaptable, computer-controlled players need to recognize their opponents' behaviour, their goals, and their plans to achieve those goals. In this paper we analyze the algorithmic challenges behind behaviour recognition in RTS games and discuss a generic RTS behaviour recognition system that we are developing to address those challenges. The application domain is that of RTS games, but many of the key points we discuss also apply to other video game genres such as multiplayer first person shooter (FPS) games.


Learning to Extract Quality Discourse in Online Communities

AAAI Conferences

Collaborative filtering systems have been developed to manage information overload and improve discourse in online communities. In such systems, users rank content provided by other users on the validity or usefulness within their particular context. The goal is that "good" content will rise to prominence and "bad" content will fade into obscurity. These filtering mechanisms are not well-understood and have known weaknesses. For example, they depend on the presence of a large crowd to rate content, but such a crowd may not be present. Additionally, the community's decisions determine which voices will reach a large audience and which will be silenced, but it is not known if these decisions represent "the wisdom of crowds" or a "censoring mob." Our approach uses statistical machine learning to predict community ratings. By extracting features that replicate the community's verdict, we can better understand collaborative filtering, improve the way the community uses the ratings of their members, and design agents that augment community decision-making. Slashdot is an example of such a community where peers will rate each others' comments based on their relevance to the post. This work extracts a wide variety of features from the Slashdot metadata and posts' linguistic contents to identify features that can predict the community rating. We find that author reputation, use of pronouns, and author sentiment are salient. We achieve 76% accuracy predicting community ratings as good, neutral, or bad.


Mixed-Initiative, Entity-Centric Data Aggregation using Assistopedia

AAAI Conferences

Wikis allow for collaborators to collect information about entities. In turn, such entity information can be used for AI tasks, such as information extraction. However, these collaborators are almost exclusively human users. Allowing arbitrary software agents to act as collaborators can greatly enrich a wiki since agents can contribute structured data to complement the human-contributed, unstructured-data. For instance, agents can import huge volumes of structured data about entities, enriching the pages, and agents can update wiki pages to reflect real-time information changes (e.g., win-loss records in sports). This paper describes an approach that allows for both arbitrary software agents and human users to collaborate. In particular, we address three key problems: agents updating the correct wiki pages, policies for agent updates, and sharing the schema across collaborators. Using our approach, we describe creating entity-focused wikis which include the ability to create dynamic categories of entities based on their wiki pages. These categories dynamically update their membership based upon real-world changes.


A Computational Decision Theory for Interactive Assistants

AAAI Conferences

We study several classes of interactive assistants from the points of view of decision theory and computational complexity. We first introduce a special class of POMDPs called hidden-goal MDPs (HGMDPs), which formalize the problem of interactively assisting an agent whose goal is hidden and whose actions are observable. In spite of its restricted nature, we show that optimal action selection in finite horizon HGMDPs is PSPACE-complete even in domains with deterministic dynamics. We then introduce a more restricted model called helper action MDPs (HAMDPs), where the assistant’s action is accepted by the agent when it is helpful, and can be easily ignored by the agent otherwise. We show classes of HAMDPs that are complete for PSPACE and NP along with a polynomial time class. Furthermore, we show that for general HAMDPs a simple myopic policy achieves a regret, compared to an omniscient assistant, that is bounded by the entropy of the initial goal distribution. A variation of this policy is also shown to achieve worst-case regret that is logarithmic in the number of goals for any goal distribution.


Bridging Common Sense Knowledge Bases with Analogy by Graph Similarity

AAAI Conferences

Present-day programs are brittle as computers are notoriously lacking in common sense. While significant progress has been made in building large common sense knowledge bases, they are intrinsically incomplete and inconsistent. This paper presents a novel approach to bridging the gaps between multiple knowledge bases, making it possible to answer queries based on knowledge collected from multiple sources without a common ontology. New assertions are found by computing graph similarity with principle component analysis to draw analogies across multiple knowledge bases. Experiments are designed to find new assertions for a Chinese commonsense knowledge base using the OMCS ConceptNet and similarly for WordNet. The assertions are voted by online users to verify that 75.77% / 77.59% for Chinese ConceptNet / WordNet respectively are good, despite the low overlap in coverage among the knowledge bases.


Visual and Spatial Factors in a Bayesian Reasoning Framework for the Recognition of Intended Messages in Grouped Bar Charts

AAAI Conferences

The overall goal of our research is the automatic recognition of the intended message of a grouped bar chart. This paper presents our preliminary work on a system that utilizes the communicative signals in a grouped bar chart as evidence in a Bayesian network that hypothesizes the primary message conveyed by the graphic. The paper discusses the kinds of communicative signals present in grouped bar charts and an ACT-R model for computationalizing one important communicative signal, the relative effort involved in performing the perceptual tasks necessary for the recognition. It also describes our Bayesian network and its implementation on a subset of the kinds of messages that can be conveyed by grouped bar charts.


Decentralised Metacognition in Context-Aware Autonomic Systems: Some Key Challenges

AAAI Conferences

A distributed non-hierarchical metacognitive architec- ture is one in which all meta-level reasoning compo- nents are subject to meta-level monitoring and manage- ment by other components. Such metacognitive distri- bution can support the robustness of distributed IT sys- tems in which humans and artificial agents are partic- ipants. However, robust metacognition also needs to be context-aware and use diversity in its reasoning and analysis methods. Both these requirements mean that an agent evaluates its reasoning within a “bigger picture” and that it can monitor this global picture from multi- ple perspectives. In particular, social context-awareness involves understanding the goals and concerns of users and organisations. In this paper, we first present a conceptual architecture for distributed metacognition with context-awareness and diversity. We then consider the challenges of apply- ing this architecture to autonomic management systems in scenarios where agents must collectively diagnose and respond to errors and intrusions. Such autonomic systems need rich semantic knowledge and diverse data sources in order to provide the necessary context for their metacognitive evaluations and decisions.


Hierarchical Planning for Mobile Manipulation

AAAI Conferences

Humans somehow manage to choose quite intelligently planner should fill in to produce a concrete plan that accomplishes the 20 trillion primitive motor commands that constitute a the goal as quickly as possible. It has long been thought that hierarchical structure in Planning at multiple levels of abstraction has long been a behavior is essential in managing this complexity. For instance, Shakey the exists at many levels, ranging from small (hundred-step?) robot used STRIPS for high-level task planning, then called motor programs for typing characters and saying phonemes out to separate low-level planning/control algorithms to execute up to large (billion-step?) actions such as writing an ICAPS each of the planned actions (Fikes and Nilsson 1971). This hard separation of levels, where a high-level plan is We believe that leveraging hierarchical structure will be chosen before considering low-level details, greatly simplifies equally important in achieving robust, efficient robotic behaviors. However, the resulting plans While your household robot probably won't get may be inefficient or even infeasible due to missed lowerlevel tenure anytime soon, even simple domestic tasks still have synergies and conflicts.


MCRNR: Fast Computing of Restricted Nash Responses by Means of Sampling

AAAI Conferences

This paper presents a sample-based algorithm for the computation of restricted Nash strategies in complex extensive form games. Recent work indicates that regret-minimization algorithms using selective sampling, such as Monte-Carlo Counterfactual Regret Minimization (MCCFR), converge faster to Nash-equilibrium (NE) strategies than their non-sampled counterparts which perform a full tree traversal. In this paper, we show that MCCFR is also able to establish NE strategies in the complex domain of Poker. Although such strategies are defensive (i.e. safe to play), they are oblivious to opponent mistakes. We can thus achieve better performance by using (an estimation of) opponent strategies. The Restricted Nash Response (RNR) algorithm was proposed to learn robust counter-strategies given such knowledge. It solves a modified game, wherein it is assumed that opponents play according to a fixed strategy with a certain probability, or to a regret-minimizing strategy otherwise. We improve the rate of convergence of the RNR algorithm using sampling. Our new algorithm, MCRNR, samples only relevant parts of the game tree. It is therefore able to converge faster to robust best-response strategies than RNR.We evaluate our algorithm on a variety of imperfect information games that are small enough to solve yet large enough to be strategically interesting, as well as a large game, Texas Hold’em Poker.