AAAI-13: THE TWENTY-SEVENTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE

# AAAI ON WEDNESDAY, JULY 17TH, 2013

Days:
previous day
next day
all days
09:00-10:00 Session 22: Invited talk: Bennett
 09:00 AAAI-13 Invited Talk: Fighting the Tuberculosis Pandemic Using Machine LearningSPEAKER: Kristin BennettABSTRACT. Tuberculosis (TB) infects one third of the world's population and is the second leading cause of death from a single infectious agent worldwide. The emergence of drug resistant TB remains a constant threat. We examine how machine learning methods can help control tuberculosis. DNA fingerprints of Mycobacterium tuberculosis complex bacteria (Mtb) are routinely gathered from TB patient isolates for every tuberculosis patient in the United States to support TB tracking and control efforts. We develop learning models to predict the genetic lineages of Mtb based on DNA fingerprints. Mining of tuberculosis patient surveillance data with respect to these genetic lineages helps discover outbreaks, improve TB control, and reveal Mtb phenotype differences. We discuss learning- and visualization-based tools to support public health efforts towards TB control in development for the New York City Health Department.
10:00-10:20Coffee Break
10:20-11:20 Session 23A: AI in Science
 10:20 Mixed Heuristic Local Search for Protein Structure PredictionSPEAKER: unknownABSTRACT. Protein structure prediction is an unsolved problem in computational biology. One great difficulty is due to the unknown factors in the actual energy function. Moreover, the energy models available are often not very informative particularly when spatially similar structures are compared during search. We introduce several novel heuristics to augment the energy model and present a new local search algorithm that exploits these heuristics in a mixed fashion. Although the heuristics individually are weaker in performance than the energy function, their combination interestingly produces stronger results. For standard benchmark proteins on the face centered cubic lattice and a realistic 20x20 energy model, we obtain structures with significantly lower energy than those obtained by the state-of-the-art algorithms. We also report results for these proteins using the same energy model on the cubic lattice. 10:35 Ranking Scientific Articles by Exploiting Citations, Authors, Journals and Time InformationSPEAKER: Yujing WangABSTRACT. Ranking scientific articles is an important but challenging task, partly due to the dynamic nature of the evolving publication network. In this paper, we mainly focus on two problems: (1) how to rank articles in the heterogeneous network; and (2) how to use time information in the dynamic network in order to obtain a better ranking result. To tackle the problems, we propose a graph-based ranking method, which utilizes citations, authors, journals/conferences and the publication time information collaboratively. The experiments were carried out on two public datasets. The result shows that our approach is practical and ranks scientific articles more accurately than the state-of-art methods. 10:50 A Morphogenetically Assisted Design Variation ToolSPEAKER: Aaron AdlerABSTRACT. The complexity and tight integration of electromechanical systems often makes them "brittle" and hard to modify in response to changing requirements. We aim to remedy this by capturing expert knowledge as functional blueprints, an idea inspired by regulatory processes that occur in natural morphogenesis. We then apply this knowledge in an intelligent design variation tool. When a user modifies a design, our tool uses functional blueprints to modify other components in response, thereby maintaining integration and reducing the need for costly search or constraint solving. In this paper, we refine the functional blueprint concept and discuss practical issues in applying it to electromechanical systems. We then validate our approach with a case study applying our prototype tool to create variants of a miniDroid robot and by empirical evaluation of convergence dynamics of networks of functional blueprints. 11:05 Guiding Scientific Discovery with Explanations Using DEMUDSPEAKER: Kiri WagstaffABSTRACT. In the era of large scientific data sets, there is an urgent need for methods to automatically prioritize data for review. At the same time, for any automated method to be adopted by scientists, it must make decisions that they can understand and trust. In this paper, we propose Discovery through Eigenbasis Modeling of Uninteresting Data (DEMUD), which uses principal components modeling and reconstruction error to prioritize data. DEMUD’s major advance is to offer domain-specific explanations for its prioritizations. We evaluated DEMUD’s ability to quickly identify diverse items of interest and the value of the explanations it provides. We found that DEMUD performs as well or better than existing class discovery methods and provides, uniquely, the first explanations for why those items are of interest. Further, in collaborations with planetary scientists, we found that DEMUD (1) quickly identifies very rare items of scientific value, (2) maintains high diversity in its selections, and (3) provides explanations that greatly improve human classification accuracy.
10:20-11:20 Session 23B: Nearest Neighbors and Hierarchical Clustering
 10:20 Discovering Hierarchical Structure for Sources and EntitiesSPEAKER: unknownABSTRACT. In this paper, we consider the problem of jointly learning hierarchies over a set of sources and entities based on their containment relationship. We model the concept of hierarchy using a set of latent binary features and propose a generative model that assigns those latent features to sources and entities in order to maximize the probability of the observed containment. To avoid fixing the number of features beforehand, we consider a non-parametric approach based on the Indian Buffet Process. The hierarchies produced by our algorithm can be used for completing missing associations and discovering structural bindings in the data. Using simulated and real datasets we provide empirical evidence of the effectiveness of the proposed approach in comparison to the existing hierarchy agnostic approaches. 10:35 Walking on Minimax Paths for k-NN SearchSPEAKER: unknownABSTRACT. Link-based dissimilarity measures, such as shortest path or Euclidean commute time distance, base their distance on paths between nodes of a weighted graph. These measures are known to be better suited to data manifold with nonconvex-shaped clusters, compared to Euclidean distance, so that k-nearest neighbor (NN) search is improved in such metric spaces. In this paper we present a new link-based dissimilarity measure based on minimax paths between nodes. Two main benefits of minimax path-based dissimilarity measure are: (1) only a subset of paths is considered to make it scalable, while Euclidean commute time distance considers all possible paths; (2) it better captures nonconvex-shaped cluster structure, compared to shortest path distance. We define the total cost assigned to a path between nodes as L_p norm of intermediate costs of edges involving the path, showing that minimax path emerges from our L_p norm over paths framework. We also define minimax distance as the intermediate cost of the longest edge on the minimax path, then present a greedy algorithm to compute k smallest minimax distances between a query and N data points in O(log N + klog k) time. Numerical experiments demonstrate that our minimax k-NN algorithm reduce the search time by several orders of magnitude, compared to existing methods, while the quality of k-NN search is significantly improved over Euclidean distance. 10:50 Formalizing Hierarchical Clustering as Integer Linear ProgrammingSPEAKER: unknownABSTRACT. Hierarchical clustering is typically implemented as a greedy heuristic algorithm with no explicit objective function. In this work we formalize hierarchical clustering as an integer linear programming (ILP) problem with a natural objective function and the dendrogram properties enforced as linear constraints. Though exact solvers exists for ILP we show that a simple randomized algorithm and a linear programming (LP) relaxation can be used to provide approximate solutions faster. Formalizing hierarchical clustering also has the benefit that relaxing the constraints can produce novel problem variations such as overlapping clusterings. Our experiments show that our formulation is capable of outperforming standard agglomerative clustering algorithms in a variety of settings, including traditional hierarchical clustering as well as learning overlapping clusterings. 11:05 Reciprocal Hash Tables for Nearest Neighbor SearchSPEAKER: unknownABSTRACT. Recent years have witnessed the success of hashing techniques in approximate nearest neighbor search. In practice, multiple hash tables are usually employed to retrieve more desired results from all hit buckets of each table. However, there are rare works studying the unified approach to constructing multiple informative hash tables except the widely used random way. In this paper, we regard the table construction as a selection problem over a set of candidate hash functions. With the graph representation of the function set, we propose an efficient solution that sequentially applies normalized dominant set to finding the most informative and independent hash functions for each table. To further reduce the redundancy between tables, we explore the reciprocal hash tables in a boosting manner, where the hash function graph is updated with high weights emphasized on the misclassified neighbor pairs of previous hash tables. The construction method is general and compatible with different types of hashing algorithms using different feature spaces and/or parameter settings. Extensive experiments on two large-scale benchmarks demonstrate that the proposed method outperforms both naive construction method and state-of-the-art hashing algorithms, with up to 65.93% accuracy gains.
10:20-11:20 Session 23C: Teamwork
10:20-11:20 Session 23D: Robot Motion Planning
 10:20 Robot Motion Planning with Dynamics as Hybrid SearchSPEAKER: Erion PlakuABSTRACT. This paper presents a general framework for motion planning with dynamics as hybrid search over the continuous space of feasible motions and the discrete space of a low-dimensional decomposition. Each step of the hybrid search consists of expanding a frontier of regions in the discrete space using cost heuristics as guide followed by sampling-based motion planning to expand a tree of feasible motions in the continuous space to reach the frontier. Comparisons to related work show significant computational speedups. 10:35 GSMDPs for Multi-Robot Sequential Decision-MakingSPEAKER: unknownABSTRACT. Markov Decision Processes (MDPs) provide an extensive theoretical background for problems of decision-making under uncertainty. In order to maintain computational tractability, however, real-world problems are typically discretized in states and actions as well as in time. Assuming synchronous state transitions and actions at fixed rates may result in models which are not strictly Markovian, or where agents are forced to idle between actions, losing their ability to react to sudden changes in the environment. In this work, we explore the application of Generalized Semi-Markov Decision Processes (GSMDPs) to a realistic multi-robot scenario. A case study will be presented in the domain of cooperative robotics, where real-time reactivity must be preserved, and therefore synchronous discrete-time approaches are sub-optimal. This case study is tested on a team of real robots, and also in realistic simulation. By allowing asynchronous events to be modeled over continuous time, the GSMDP approach is shown to provide greater solution quality than its discrete-time counterparts, while still being approximately solvable by existing methods. 10:50 A Simple, But NP-Hard, Motion Planning ProblemSPEAKER: unknownABSTRACT. Determining the existence of a collision-free path between two points is one of the most fundamental questions in robotics. However, in situations where crossing an obstacle is costly but not impossible, it may be more appropriate to ask for the path that crosses the fewest obstacles. This may arise in both autonomous outdoor navigation (where the obstacles are rough but not completely impassable terrain) or indoor navigation (where the obstacles are doors that can be opened if necessary). This problem, the minimum constraint removal problem, is at least as hard as the underlying path existence problem. In this paper, we demonstrate that the minimum constraint removal problem is NP-hard for navigation in the plane even when the obstacles are all convex, a case where the path existence problem is very easy. 11:05 Structure and Intractability of Optimal Multi-robot Path Planning on GraphsSPEAKER: unknownABSTRACT. In this paper, we study the structure and computational complexity of optimal multi-robot path planning problems on graphs. Our results encompass three formulations of the discrete multi-robot path planning problem, including a variant that allows synchronous rotations of robots along fully occupied, disjoint cycles on the graph. Allowing rotation of robots provides a more natural model for multi-robot path planning because robots can communicate. The optimality objectives that we study are total arrival time, makespan (last arrival time), and total distance. On the structure side, we show that, when there are two or more unoccupied vertices, these objectives demonstrate a pairwise Pareto optimal structure and cannot be simultaneously optimized. On the computational complexity side, we extend previous work and show that, regardless of the underlying multi-robot path planning problem, these objectives are all intractable to compute. In particular, our NP-hardness proof for the time optimal versions, based on a simple and direct reduction from the 3-satisfiability problem, shows that these problems remain NP-hard even when there are only two groups of robots (i.e. robots within each group are interchangeable).
10:20-11:20 Session 23E: Spotlights and Senior Members
 10:20 A filtering algorithm for constraints of difference in CSPsSPEAKER: unknownABSTRACT. Classic Paper Award from 1994. 10:35 Acting Optimally in Partially Observable Stochastic DomainsSPEAKER: unknownABSTRACT. Classic Paper Award from 1994. 10:50 Decision-Making in Open Mixed NetworksSPEAKER: Kobi GalABSTRACT. Computer systems are increasingly being deployed in group settings in which they interact with people as well as with other computer agents. We refer to these heterogeneous groups of people and computer agents as open mixed networks'' to reflect the inclusion of people, the distributed nature of agents in the group (designed by or representing different people and organizations) and the network-like relationships that connect all of the participants in their endeavours. Despite the growing prevalence of mixed networks, the design of agents that perform well in these networks has received less attention than the design of agents for settings comprising solely computer agents. It has been shown that results obtained in such homogeneous computational settings may not hold once people are in the loop''. To meet the challenges associated with agent-design for open-mixed networks a new research focus in AI is required. My proposed talk will present advances and lay out the challenges in this newly emerging area focusing on three research directions. (1) Reasoning and representing social and psychological factors; (2) Factored representations and learning from sparse data; (3) Novel empirical frameworks and methodologies.
10:20-11:20 Session 23G: Language Processing
 10:20 AAAI-13 Outstanding Paper, Honorable Mention: Effective Bilingual Constraints for Semi-supervised Learning of Named Entity RecognizersSPEAKER: Mengqiu WangABSTRACT. Most semi-supervised methods in Natural Language Processing capitalize on unannotated resources in a single language; however, information can be gained from using parallel resources in more than one language, since translations of the same utterance in different languages can help to disambiguate each other. We demonstrate a method that makes effective use of vast amounts of bilingual text (a.k.a. bitext) to improve monolingual systems. We propose a factored probabilistic sequence model that encourages both crosslanguage and intra-document consistency. A simple Gibbs sampling algorithm is introduced for performing approximate inference. Experiments on English-Chinese Named Entity Recognition (NER) using the OntoNotes dataset demonstrate that our method is significantly more accurate than state-of-the-art monolingual CRF models in a bilingual test setting. Our model also improves on previous work by Burkett et al. (2010), achieving a relative error reduction of 10.8% and 4.5% in Chinese and English, respectively. Furthermore, by annotating a moderate amount of unlabeled bi-text with our bilingual model, and using the tagged data for uptraining, we achieve a 9.2% error reduction in Chinese over the state-of-the-art Stanford monolingual NER system. 10:35 Grounding Natural Language References to Unvisited and Hypothetical LocationSPEAKER: unknownABSTRACT. While much research exists on resolving spatial natural language references to known locations, little work deals with handling references to unknown locations. In this paper we introduce and evaluate algorithms integrated into a cognitive architecture which allow an agent to learn about its environment while resolving references to both known and unknown locations. We also describe how multiple components jointly facilitate these capabilities. 10:50 An Extended GHKM Algorithm for Inducing Lambda-SCFGSPEAKER: Peng LiABSTRACT. Semantic parsing, which aims at mapping a natural language (NL) sentence into its formal meaning representation (e.g., logical form), has received increasing attention in recent years. While synchronous context-free grammar (SCFG) augmented with lambda calculus (lambda-SCFG) provides an effective mechanism for semantic parsing, how to learn such lambda-SCFG rules still remains a challenge because of the difficulty in determining the correspondence between NL sentences and logical forms. To alleviate this structural divergence problem, we extend the GHKM algorithm, which is a state-of-the-art algorithm for learning synchronous grammars in statistical machine translation, to induce lambda-SCFG from pairs of NL sentences and logical forms. By treating logical forms as trees, we reformulate the theory behind GHKM that gives formal semantics to the alignment between NL words and logical form tokens. Experiments on the GEOQUERY dataset show that our semantic parser achieves an F-measure of 90.2%, the best result published to date. 11:05 Automatic Identification of Conceptual Metaphors With Limited KnowledgeSPEAKER: unknownABSTRACT. Complete natural language understanding requires identifying and analyzing the meanings of metaphors, which are ubiquitous in text and speech. Underlying metaphors in language are conceptual metaphors, partial semantic mappings between disparate conceptual domains. Though positive results have been achieved in identifying linguistic metaphors over the last decade, little work has been done to date on automatically identifying conceptual metaphors. This paper describes research on identifying conceptual metaphors based on corpus data. Our method uses as little background knowledge as possible, to ease transfer to new languages and to minimize any bias introduced by the knowledge base construction process. The method relies on general heuristics for identifying linguistic metaphors and statistical clustering (guided by Wordnet) to form conceptual metaphor candidates. Human experiments show the system effectively finds meaningful conceptual metaphors.
11:20-12:20 Session 24A: Bribery / Voting
 11:20 Computational Aspects of Nearly Single-Peaked ElectoratesSPEAKER: unknownABSTRACT. Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting systems are in the general case computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these systems suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the complexity of dishonest behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure. In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is in many cases NP-complete. For one case we present a polynomial-time algorithm. Furthermore, we explore the relations between several notions of nearly single-peakedness and study the complexity of manipulation for nearly single-peaked elections. 11:35 Ties Matter: Complexity of Manipulation when Tie-breaking with a Random VoteSPEAKER: unknownABSTRACT. We study the impact on strategic voting of tie-breaking by means of considering the order of tied candidates within a random vote. We compare this to another non-deterministic tie-breaking rule where we simply choose between candidates uniformly at random. In general, we demonstrate that there is no connection between the computational complexity of computing a manipulating vote with the two different types of tie-breaking. However, we prove that for some scoring rules, the computational complexity of computing a manipulation can increase from polynomial to NP-hard. We also discuss the relationship with the computational complexity of computing a manipulating vote when we ask for an unique winner, or when we select from the set of co-winners. 11:50 Bribery in Voting with Soft ConstraintsSPEAKER: unknownABSTRACT. We consider a multi-agent scenario where a collection of agents needs to select a common decision from a large set of possible decisions, over which they express their preferences. Such a decision set has a combinatorial structure, that is, each candidate is an element of the Cartesian product of the domains of some variables. We assume agents compactly express their preferences over the candidates via soft constraints. We consider various aggregation methods: some are sequential, in the sense that they aggregate the preferences over one variable at a time, and an other one is one-step, i.e., it aggregates the preferences over complete assignments of the variables. We study the complexity of influencing such aggregation methods through bribery: How computationally complex is it for an external agent to determine whether by paying certain agents to change their preferences, within a certain budget, a specified candidate can be made the winner decision? We prove that bribery is NP-complete for the considered sequential aggregation methods (based on Plurality, Approval, and Borda) for most of the cost schemes we defined, while the problem is polynomial for one-step Plurality. 12:05 How Bad is Selfish Voting?SPEAKER: unknownABSTRACT. It is well known that strategic behavior in elections is essentially unavoidable; we therefore ask: how bad can the rational outcome be? We answer this question via the notion of the price of anarchy, using the scores of alternatives as a proxy for their quality and bounding the ratio between the score of the optimal alternative and the score of the winning alternative in Nash equilibrium. Specifically, we are interested in Nash equilibria that are obtained via sequences of rational strategic moves. Focusing on three common voting rules — plurality, veto, and Borda — we provide very positive results for plurality and very negative results for Borda, and place veto in the middle of this spectrum.
11:20-12:20 Session 24B: Planning
 11:20 Hypothesis Exploration for Malware Detection Using PlanningSPEAKER: unknownABSTRACT. In this paper we apply AI planning to address the hypothesis exploration problem and provide assistance to network administrators in detecting malware based on unreliable observations derived from network traffic.Building on the already established characterization and use of AI planning for similar problems, we propose a formulation of the hypothesis generation problem for malware detection as an AI planning problem with temporally extended goals and actions costs. Furthermore, we propose a notion of hypothesis plausibility'' under unreliable observations, which we model as plan quality. We then show that in the presence of unreliable observations, simply finding one most plausible'' hypothesis, although challenging, is not sufficient for effective malware detection. To that end, we propose a method for applying a state-of-the-art planner within a principled exploration process, to generate multiple distinct high-quality plans. We experimentally evaluate this approach by generating random problems of varying hardness both with respect to the number of observations, as well as the degree of unreliability. Based on these experiments, we argue that our approach presents a significant improvement over prior work that are focused on finding a single optimal plan, and that the hypothesis exploration application can motivate the development of new planners capable of generating the top high-quality plans. 11:35 Red-Black Relaxed Plan HeuristicsSPEAKER: unknownABSTRACT. Despite its success, the delete relaxation has significant pit- falls in many important classes of planning domains. Recent work has devised the red-black planning framework, where red variables take the relaxed semantics, in which they accumulate their values rather than switching between them, as opposed to black variables that take the regular semantics. Provided the red variables are chosen so that red-black plan generation is tractable, one can generate such a plan for every search state, and take its length as the heuristic distance estimate. Previous results were not suitable for this purpose because they identified tractable fragments for red-black plan existence, as opposed to red-black plan generation. We identify a new fragment of red-black planning, that fixes this issue. We devise machinery to efficiently generate red-black plans, and to automatically select the red variables. Experiments show that the resulting heuristics can significantly improve over standard delete relaxation heuristics. 11:50 Truncated Incremental Search: Faster Replanning by Exploiting SuboptimalitySPEAKER: unknownABSTRACT. Incremental heuristic searches try to reuse their previous search efforts whenever these are available. As a result, they can often solve a sequence of similar planning problems much faster than planning from scratch. State-of-the-art incremental heuristic searches such as LPA*, D* and D* Lite all work by propagating cost changes to all the states on the search tree whose g-values (the costs of computed paths from the start) are no longer optimal. While such a complete propagation of cost changes is required to ensure optimality, the propagations can be stopped much earlier if we are looking for solutions within a given suboptimality bound. We develop an algorithm called Truncated LPA* (TLPA*), that builds on this observation, and uses a target suboptimality bound to efficiently restrict the cost propagations. We explain TLPA*, discuss its analytical properties and present experimental results for 2D and 3D (x, y, heading) path planning that show significant improvement in runtime over existing incremental heuristic searches when searching for close-to-optimal solutions. In addition, unlike typical incremental searches, TLPA* is much less dependent on the proximity of the cost changes to the goal of the search due to the early termination of the cost change propagation. 12:05 A First-Order Formalization of Commitments and Goals for PlanningSPEAKER: unknownABSTRACT. Commitments have been shown to model interactions in multiagent systems in a computationally realizable yet high-level manner without compromising the autonomy and heterogeneity of the member agents. Recent work has shown how to combine commitments with goals and apply methods such as planning by which agents can determine their actions. However, previous approaches to modeling commitments have been confined to propositional representations, which limits their applicability in practical cases. We propose a first-order representation and reasoning technique for commitments and goals that accommodates settings where the commitments and goals are templatic and may be applied repeatedly with differing bindings for domain objects. Doing so not only leads to a more perspicuous modeling, it also enables us to support a variety of practical patterns. In particular, our approach can handle the piecemeal progress, consolidation, delegation, and compensation of commitments.
11:20-12:20 Session 24C: Situation Calculus and STRIPS
 11:20 Multiagent Knowledge and Belief Change in the Situation CalculusSPEAKER: unknownABSTRACT. Belief change is an important research area in Artificial Intelligence. It becomes more perplexing in the presence of multiple agents, since the action of an agent may be partially observable to other agents. In this paper, we present a general approach to reasoning about actions and belief change in multi-agent scenarios. Our approach is based on a multi-agent extension to the situation calculus, augmented by a plausibility relation over situations and another one over actions, which is used to represent agents' different perspectives on actions. When an action is performed, we update the agents' plausibility order over situations by giving priority to the plausibility order over actions, in line with the AGM approach of giving priority to new information. We show that our notion of belief satisfies KD45 properties. When it comes to the special case of belief change of a single agent, we show that our framework satisfies most of the classical AGM, DP, and KM postulates. Finally, we present properties concerning the change of common knowledge and belief of a group of agents. 11:35 Progression of Decomposed Situation Calculus TheoriesSPEAKER: unknownABSTRACT. In many tasks related to reasoning about consequences of a logical theory, it is desirable to decompose the theory into a number of components with weakly-related or independent signatures. This facilitates reasoning when signature of a query formula belongs to only one of the components. However, a theory may be subject to change due to execution of actions affecting features mentioned in the theory. Having once computed a decomposition of a theory, one would like to know whether a decomposition has to be computed again in the theory obtained from taking into account all changes resulting from execution of an action. In the paper, we address this problem in the scope of the situation calculus, where change of an initial theory is related to the well-studied notion of progression. Progression provides a form of forward reasoning; it relies on forgetting values of those features which are subject to change and computing new values for them. We prove new results about properties of decomposition components under forgetting and show when a decomposition can be preserved in progression of an initial situation calculus theory. 11:50 Data-Parallel Computing Meets STRIPSSPEAKER: Erez KarpasABSTRACT. The increased demand for distributed computations on “big data” has led to solutions such as SCOPE, DryadLINQ, Pig, and Hive, which allow the user to specify queries in an SQL-like language, enriched with sets of user-defined operators. The lack of exact semantics for user-defined operators interferes with the query optimization process, thus putting the burden of suggesting, at least partial, query plans on the user. In an attempt to ease this burden, we propose a formal model that allows for data-parallel program synthesis (DPPS) in a semantically well-deﬁned manner. We show that this model generalizes existing frameworks for data-parallel computation, while providing the flexibility of query plan generation that is currently absent from these frameworks. In particular, we show how existing, off-the-shelf, AI planning tools can be used for solving DPPS tasks. 12:05 Reasoning about Saturated Conditional Independence under Uncertainty: Axioms, Algorithms and Levesque's Situations to the RescueSPEAKER: Sebastian LinkABSTRACT. The implication problem of probabilistic conditional independencies is investigated in the presence of missing data. Here, graph separation axioms fail to hold for saturated conditional independencies, unlike the known idealized case with no missing data. Several axiomatic, algorithmic, and logical characterizations of the implication problem for saturated conditional independencies are established. In particular, equivalences are shown to the implication problem of a propositional fragment under Levesque's situations, and that of Lien's class of multivalued database dependencies under null values.
11:20-12:20 Session 24D: Analyzing Networks and Graphs
 11:20 Fast and Exact Top-k Algorithm for PageRankSPEAKER: unknownABSTRACT. In AI and Web communities, many applications utilize PageRank. To obtain high PageRank score nodes, the original approach iteratively computes the PageRank score of each node until convergence by using the whole graph. If the graph is large, this approach is infeasible due to its high computational cost. The goal of this study is to find top-k PageRank score nodes efficiently for a given graph without sacrificing accuracy. Our solution, F-Rank, is based on two ideas: (1) It iteratively estimates lower/upper bounds of PageRank scores, and (2) It constructs subgraphs in each iteration by pruning unnecessary nodes and edges to identify top-k nodes. Our theoretical analysis shows that F-Rank guarantees result exactness. Experiments show that F-Rank finds top-k nodes much faster than the original approach. 11:35 Heterogeneous Metric Learning with Joint Graph Regularization for Cross-Media RetrievalSPEAKER: unknownABSTRACT. As the major component of big data, unstructured heterogeneous multimedia content such as text, image, audio, video and 3D increasing rapidly on the Internet. User demand a new type of cross-media retrieval where user can search results across various media by submitting query of any media. Since the query and the retrieved results can be of different media, how to learn a heterogeneous metric is the key challenge. Most existing metric learning algorithms only focus on a single media where all of the media objects share the same data representation. In this paper, we propose a joint graph regularized heterogeneous metric learning (JGRHML) algorithm, which integrates the structure of different media into a joint graph regularization. In JGRHML, different media are complementary to each other and optimizing them simultaneously can make the solution smoother for both media and further improve the accuracy of the final metric. Based on the heterogeneous metric, we further learn a high-level semantic metric through label propagation. JGRHML is effective to explore the semantic relationship hidden across different modalities. The experimental results on two datasets with up to five media types show the effectiveness of our proposed approach. 11:50 TONIC: Target Oriented Network Intelligence Collection for the Social WebSPEAKER: unknownABSTRACT. In this paper we introduce the Target Oriented Network Intelligence Collection (TONIC) problem, which is the problem of finding profiles in a social network that contain information about a given target via automated crawling. % procedure. We formalize TONIC as a search problem and a best-first approach is proposed for solving it. Several heuristics are presented to guide this search. These heuristics are based on the topology of the currently known part of the social network. The efficiency of the proposed heuristics and the effect of the graph topology on their performance is experimentally evaluated on the Google+ social network. 12:05 Preventing Unraveling in Social Networks Gets HarderSPEAKER: unknownABSTRACT. The behavior of users in social networks is often observed to be affected by the actions of their friends. Bhawalkar et al. in ICALP 2012 introduced a formal mathematical model for user engagement in social networks where each individual derives a benefit proportional to the number of its friends which are engaged. Given a threshold degree $k$ the equilibrium for this model is a maximal subgraph whose minimum degree is $\geq k$. However the dropping out of individuals with degrees less than $k$ might lead to a cascading effect of iterated withdrawals such that the size of equilibrium subgraph becomes very small. To overcome this some special vertices called anchors" are introduced: these vertices need not have large degree. Bhawalkar et al. considered the Anchored $k$-Core problem: given a graph $G$ and integers $b, k$ and $p$, do there exist a set of vertices $B\subseteq H\subseteq V(G)$ such that $|B|\leq b, |H|\geq p$ and every vertex $v\in H\setminus B$ satisfies $\text{deg}_{G[H]} (v)\geq k$. They showed that the problem is NP-hard for $k\geq 2$ and gave some inapproximability and fixed-parameter intractability results. In this paper we give improved hardness results for this problem. In particular we show that the Anchored $k$-Core problem is W[1]-hard parameterized by $p$, even for $k=3$. This improves the result of Bhawalkar et al. (who show W[2]-hardness parameterized by $b$) as our parameter is always bigger since $p\geq b$. Then we answer a question of Bhawalkar et al. by showing that the Anchored $k$-Core problem remains NP-hard on planar graphs for all $k\geq 3$, even if the maximum degree of the graph is $k+2$. Finally we show that the problem is FPT on planar graphs parameterized by $b$ for all $k\geq 7$.
11:20-12:20 Session 24E: ML in Robotics
 11:20 Multi-Target Detection and Recognition by UAVs Using Online POMDPsSPEAKER: unknownABSTRACT. This paper tackles high-level decision-making techniques for robotic missions, which involve both active sensing and symbolic goal reaching, under uncertain probabilistic environments and strong time constraints. Our case study is a POMDP model of an online multi-target detection and recognition mission by an autonomous rotorcraft UAV. The POMDP model of the multi-target detection and recognition problem is generated on line from a list of areas of interest, which are automatically extracted at the beginning of the flight from a coarse-grained high altitude observation of the scene. The POMDP observation model relies on a statistical abstraction of the image processing algorithm's classifier output used to detect and identify targets. As the POMDP problem cannot be known and thus optimized before the beginning of the flight, our main contribution is an "optimize-while-execute" algorithmic framework: it drives a POMDP sub-planner to optimize and execute the POMDP policy in parallel under action duration constraints, reasoning about the future possible execution states of the robotic system. We present new results from real outdoor flights and software-in-the-loop simulations, which highlight both the benefits of using POMDPs in multi-target detection and recognition missions, and of our "optimize-while-execute" paradigm. 11:35 Compact RGBD Surface Models Based on Sparse CodingSPEAKER: unknownABSTRACT. In this paper, we describe a novel approach to construct compact colored 3D environment models representing local surface attributes via sparse coding. Our method decomposes a set of colored point clouds into local surface patches and encodes them based on an overcomplete dictionary. Instead of storing the entire point cloud, we store a dictionary, surface patch positions, and a sparse code description of the depth and RGB attributes for every patch. The dictionary is learned in an unsupervised way from surface patches sampled from indoor maps. We show that better dictionaries can be learned by extending the K-SVD method with a binary weighting scheme that ignores undefined surface cells. Through experimental evaluation on real world laser and RGBD datasets we demonstrate that our method produces compact and accurate models. Furthermore, we clearly outperform an existing state of the art method in terms of compactness, accuracy and computation time. Additionally, we demonstrate that our sparse code descriptions can be utilized for other important tasks including object detection. 11:50 Open-Loop Planning in Large-Scale Stochastic DomainsSPEAKER: unknownABSTRACT. We focus on effective planning in the face of high-dimensionality, underactuation, drift, discrete system changes, and stochasticity. These are hallmark challenges for important problems such as humanoid locomotion. Because generality and broad applicability of the method is desired, we assume domain expertise is minimal and limited to a generative model. We need the method to be responsive, so it must have computational costs that scale linearly with the amount of samples taken from the generative model. We bring to bear a concrete method that satisfies all these requirements; it is a receding-horizon open-loop planner that employs cross-entropy optimization for policy construction. In empirical simulations, we demonstrate near-optimal decisions in a small domain and locomotion in several challenging humanoid control tasks. 12:05 Bayesian Nonparametric Multi-Optima Policy Search in Reinforcement LearningSPEAKER: unknownABSTRACT. Skills can often be performed in many different ways. In order to provide robots with human-like adaptation capabilities, it is of great interest to consider the possibility of learning several of them in parallel, since eventual changes in the environment or in the robot can make some solutions unfeasible. In this case, the knowledge of multiple solutions can avoid to relearn the task. This problem is addressed in this paper within the framework of Reinforcement Learning, as the automatic determination of multiple optimal parameterized policies. For this purpose, a model handling a variable number of policies is built, using a Bayesian non-parametric approach. The algorithm is compared to single policy algorithms on some known benchmarks and is then applied to robotics, on problems presenting multiple solutions.
11:20-12:20 Session 24F: Spotlights and Senior Members
 11:20 RSS: What's HotSPEAKER: unknownABSTRACT. Language Grounding 11:35 CP: What's Hot and ChallengesSPEAKER: unknown 11:50 CP: ChallengesSPEAKER: unknown
12:20-12:30 Session 25A
 12:20 Multiple Outcome Supervised Latent Dirichlet Allocation for Expert Discovery in Online ForumsSPEAKER: unknownABSTRACT. This paper presents a supervised bayesian approach to model expertise in online forums with application to question routing. The proposed method extends the well-known LDA model to account for a supervised stage with multiple outputs per document, corresponding to each of the users of the system. A study of the characteristics of real world data revealed a number of challenges with interest for the community. 12:22 Supervised Topic Model with Consideration of User and ItemSPEAKER: unknownABSTRACT. In this paper, we propose a new supervised topic model by incorporating the user and the item information. The proposed model can simultaneously utilize the textual topic and user-item factors for rating prediction. We conduct rating prediction experiment with a public review data set. The results demonstrate the advantages of our model. It shows clear improvement compared with tranditional supervised topic model and recommendation method. 12:24 Combining CP-Nets with the Power of OntologiesSPEAKER: unknownABSTRACT. The Web is currently shifting from data on linked Web pages towards less interlinked data in social networks on the Web. Therefore, rather than being based on the link structure between Web pages, the ranking of search results needs to be based on something new. We believe that it can be based on user preferences and ontological background knowledge, as a means to personalized access to information. There are many approaches to preference representation and reasoning in the literature. The most prominent qualitative ones are perhaps CP-nets. Their clear graphical structure unifies an easy representation of preferences with nice properties when computing the best outcome. In this paper, we introduce {\em ontological CP-nets}, where the knowledge domain has an ontological structure, i.e., the values of the variables are constrained relative to an underlying ontology. We show how the computation of Pareto optimal outcomes for such ontological CP-nets can be reduced to the solution of constraint satisfaction problems. We also provide several complexity and tractability results. 12:26 Negative Influence Minimizing by Blocking Nodes in Social NetworksSPEAKER: unknownABSTRACT. Social networks are becoming vital platforms for the spread of positive information such as innovations and negative information propagation like malicious rumors. In this paper, we address the problem of minimizing the influence of negative information. When negative information such as a rumor emerges in the social network and part of users have already adopted it, our goal is to minimize the size of ultimately contaminated users by discovering and blocking k uninfected users. A greedy method for efficiently finding a good approximate solution to this problem is proposed. The comparison experimental results on the Enron email network dataset demonstrate our proposed method is more effective than centrality based methods, such as degree centrality, betweenness centrality and PageRank.
12:20-12:30 Session 25B
 12:20 Comprehensive Cross-Hierarchy Cluster Agreement EvaluationSPEAKER: unknownABSTRACT. Hierarchical clustering represents a family of widely used clustering approaches that can organize objects into a hierarchy based on the similarity in objects' feature values. One significant obstacle facing hierarchical clustering research today is the lack of general and robust evaluation methods. Existing works rely on a range of evaluation techniques including both internal (no ground-truth is considered in evaluation) and external measures (results are compared to ground-truth semantic structure). The existing internal techniques may have strong hierarchical validity, but the available external measures were not developed specifically for hierarchies. This lack of specificity prevents them from comparing hierarchy structures in a holistic, principled way. To address this problem, we propose the Hierarchy Agreement Index, a novel hierarchy comparison algorithm that holistically compares two hierarchical clustering results (e.g. ground-truth and automatically learned hierarchies) and rates their structural agreement on a 0-1 scale. We compare the proposed evaluation method with a baseline approach (based on computing F-Score results between individual nodes in the two hierarchies) on a set of unsupervised and semi-supervised hierarchical clustering results, and observe that the proposed Hierarchy Agreement Index provides more intuitive and reasonable evaluation of the learned hierarchies. 12:22 Strong Nash Equilibrium Is in Smoothed PSPEAKER: unknownABSTRACT. The computational characterization of game--theoretic solution concepts is a prominent topic in artificial intelligence. The central solution concept is Nash equilibrium (NE). However, it fails to capture the possibility that agents can form coalitions. Strong Nash equilibrium (SNE) refines NE to this setting. It is known that finding an SNE is NP-complete when the number of agents is constant. This hardness is solely due to the existence of mixed--strategy SNEs, given that the problem of enumerating all pure-strategy SNEs is trivially in P. Our central result is that, in order for a n-agent game to have at least one non-pure-strategy SNE, the agents' payoffs restricted to the agents' supports must lie on an (n-1)-dimensional space. Small perturbations make the payoffs to be outside such a space and thus, unlike NE, finding an SNE is in smoothed polynomial time. 12:24 Verbal IQ of a Four-Year Old Achieved by an AI SystemSPEAKER: unknownABSTRACT. Verbal tasks that have traditionally been difficult for computer systems but are easy for young children are among AI’s “grand challenges”. We present the results of testing the ConceptNet 4 system on the verbal part of the standard WPPSI-III IQ test, using simple test-answering algorithms. It is found that the system has the Verbal IQ of an average four-year-old child. 12:26 Approximation of Lorenz-Optimal Solutions in Multiobjective Markov Decision ProcessesSPEAKER: unknownABSTRACT. We describe and test algorithms for finding small, representative subsets of the Lorenz-optimal policies for Multiobjective Markov Decision Processes. 12:28 Covering Landmark Interactions for Semantically Diverse PlansSPEAKER: Daniel BryceABSTRACT. Prior approaches to generating diverse plans in domain-independent planning seek out syntactic variations on plan structure such as actions or causal links used, or states entered. As a result, syntactic approaches can achieve great plan set diversity by synthesizing unnecessarily long plans. This type of misleading diversity may be useful if, for example, the plans are used as training data for a learner; however, they have arguably low value to a human decision maker. We present an approach to domain-independent diverse planning that systematically varies the semantic attributes of plans so that we do not arbitrarily inflate plan length to achieve syntactic diversity. Our contribution is based upon the fact that landmarks, which represent the minimally necessary subgoals (semantics) of a planning domain, can be disjunctive and hence satisfied in a number of ways. Varying the disjuncts that must be satisfied by alternative plans leads to a form of diversity that does not encourage irrelevant plan structure. We present an extension of the LAMA planner called DLAMA that generates multiple plans, each required to systematically satisfy alternative landmark disjuncts. We show that, in comparison with syntacticly diverse planners, DLAMA reduces average plan length while achieving plan set diversity.
12:20-12:30 Session 25C
12:20-12:30 Session 25D
 12:20 Modular Answer Set SolvingSPEAKER: unknownABSTRACT. Modularity is essential for modeling large-scale practical applications. We propose modular logic programs as a modular version of answer set programming and study the relationship of our formalism to an earlier concept of lp-modules. 12:22 Additive Counterexample-guided Cartesian Abstraction RefinementSPEAKER: unknownABSTRACT. We recently showed how counterexample-guided abstraction refinement can be used to derive informative heuristics for optimal classical planning. In this work we introduce an algorithm for building additive abstractions and demonstrate that they outperform other state-of-the-art abstractions heuristics on many benchmark domains. 12:24 Partial Domain Search Tree for Constraint-Satisfaction ProblemsSPEAKER: unknownABSTRACT. CSP Solvers usually search the partial assignment search tree. We present a new formalization that spans a conceptually different search tree, where each node represents subsets of the original domains for the variables. We experiment with a simple backtracking algorithm for this search tree and show that it outperforms a simple backtracking algorithm on the traditional search tree in many cases. 12:26 Volatile Multi-Armed Bandits for Guaranteed Targeted Social CrawlingSPEAKER: unknownABSTRACT. We introduce a new variant of multi-armed bandit, called Volatile-multi-arm bandit problem (VMAB) and provide a policy with bounded regret. We show how the problem of collecting intelligence on profiles in social networks can be modeled as a VMAB and demonstrate experimentally the superiority of our proposed policy. 12:28 Localizing Web Videos from Heterogeneous ImagesSPEAKER: unknownABSTRACT. While geo-localization of web images has been widely studied, there is limited work that touches the geolocation inference of web videos. However, such geographical localization functionality is of great importance to provide location-aware services , especially on mobile devices. In this paper, we tackle this problem from a novel perspective, by “transferring” the largescale web images with geographical tags to web videos, by making associations between their visual content similarities (e.g. near-duplicate detection between video frames and images). A group of experiments are conducted on a collected web image and video data set compared with several alternatives and stat-of-the-arts.
12:30-13:45Lunch Break
13:45-14:45 Session 26: Invited talk:Sandholm
 13:45 AAAI-13 Invited Talk: Poker AI: Algorithms for Creating Game-Theoretic Strategies for Large Incomplete-Information GamesSPEAKER: Tuomas SandholmABSTRACT. Incomplete-information games — such as most auctions, negotiations, and future (cyber)security settings — cannot be solved using minimax search even in principle. Completely different algorithms were needed. A dramatic scalability leap has occurred in our ability to solve such games over the last seven years, fueled largely by the Annual Computer Poker Competition. I will discuss the key domain-independent techniques that enabled this leap, including automated abstraction techniques and approaches for mitigating the issues that they raise, new equilibrium-finding algorithms, safe opponent exploitation methods, techniques that use qualitative knowledge as an extra input, and endgame solving techniques. I will finish by benchmarking poker programs against the best human poker professionals and by discussing what humans can learn from the programs.
14:45-15:45 Session 27A: Constraints
 14:45 Unified Constraint Propagation on Multi-View DataSPEAKER: unknownABSTRACT. This paper presents a unified framework for intra-view and inter-view constraint propagation on multi-view data from a semi-supervised learning viewpoint. In the literature, pairwise constraint propagation has been studied extensively, where each pairwise constraint is defined over a pair of data points from a single view. In contrast, very little attention has been paid to inter-view constraint propagation, which is more challenging since each pairwise constraint is now defined over a pair of data points from different views. Although both intra-view and inter-view constraint propagation are crucial for multi-view tasks, most previous methods cannot handle them simultaneously. To address this challenging issue, we propose to decompose these two types of constraint propagation into semi-supervised learning subproblems so that they can be uniformly solved based on the traditional label propagation techniques. To further integrate them into a unified framework, we utilize the results of intra-view constraint propagation to adjust the similarity matrix of each view and then perform inter-view constraint propagation with the adjusted similarity matrices. The experimental results in cross-view retrieval have demonstrated the superior performance of our unified constraint propagation. 15:00 On the Subexponential Time Complexity of CSPSPEAKER: unknownABSTRACT. A Constraint Satisfaction Problem (CSP) with n variables ranging over a domain of d values can be solved by brute-force in d^n steps (omitting a polynomial factor). With a more careful approach, this trivial upper bound can be improved for certain natural restrictions of the CSP. In this paper we establish theoretical limits to such improvements, and draw a detailed landscape of the subexponential-time complexity of CSP. We first establish relations between the subexponential-time complexity of CSP and that of other problems, including CNF-SAT. We exploit this connection to provide tight characterizations of the subexponential-time complexity of CSP under common assumptions in complexity theory. For several natural CSP parameters, we obtain threshold functions that precisely dictate the subexponential-time complexity of CSP with respect to the parameters under consideration. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving CSP. 15:15 Improving the Performance of Consistency Algorithms by Localizing and Bolstering Propagation in a Tree DecompositionSPEAKER: unknownABSTRACT. Certain classes of Constraint Satisfaction Problems (CSPs) can be solved in polynomial time when the consistency level corresponds to a structural parameter of the constraint network such as the treewidth or the hypertree width. In this work we exploit this condition and propose new techniques that allow us to practically approach the necessary consistency level. We proposed to apply the parametrized relational consistency property R(∗,m)C locally to the clusters of a tree decomposition and set the value of m to the total number of relations in the cluster. Moreover, we propose different schemes to bolster the separators to enhance the propagation. We conceptually compare the resulting new consistency properties to other consistency properties, and empirically evaluate them against GAC, maxRPWC and wR(∗,m)C. The empirical results suggest that our technique outperforms GAC, maxRPWC, and wR(∗,m)C in certain hard CSP classes. 15:30 Extending STR to a Higher-Order ConsistencySPEAKER: unknownABSTRACT. One of the most widely studied classes of constraints in constraint programming (CP) is that of table constraints. Numerous specialized filtering algorithms, enforcing the wellknown property called generalized arc consistency (GAC), have been developed for such constraints. Among the most successful GAC algorithms for table constraints, we find variants of simple tabular reduction (STR), like STR2. In this paper, we propose an extension of STR-based algorithms that achieves full pairwise consistency (FPWC), a consistency stronger than GAC and max Restricted Pairwise Consistency (maxRPWC). Our approach involves counting the number of occurrences of specific combinations of values in constraint intersections. Importantly, the worst-case time complexity of one call to the basic filtering procedure at the heart of our new algorithm is quite close to that of STR algorithms. Experiments demonstrate that our method can outperform STR2 in many classes of problems, being significantly faster in some cases. Also, it is clearly superior to maxRPWC+, an algorithm that has been recently proposed.
14:45-15:45 Session 27B: Tensors and Manifolds
 14:45 Multiscale Manifold LearningSPEAKER: unknownABSTRACT. Many high-dimensional data sets that lie on a low-dimensional manifold exhibit nontrivial regularities at multiple scales. Most work in manifold learning ignores this multiscale structure. In this paper, we propose approaches to explore the deep structures of manifolds. The proposed approaches are based on the diffusion wavelets model, data driven, and able to directly process directional neighborhood relationships without ad-hoc symmetrization. The proposed multiscale algorithms are evaluated using both synthetic and real-world data sets. 15:00 A Tensor-Variate Gaussian Process for Classification of Multidimensional Structured DataSPEAKER: unknownABSTRACT. As tensors provide a natural and efficient representation of multidimensional structured data, in this paper, we consider probabilistic multinomial probit classification for tensor-variate inputs with Gaussian processes (GP) priors placed over the latent function. In order to take into account the underlying multimodes structure information within the model, we propose a framework of probabilistic product kernels for tensorial data based on a generative model assumption. More specifically, it can be interpreted as mapping tensors to probability density function space and measuring similarity by an information divergence. Since tensor kernels enable us to model input tensor observations, the proposed tensor-variate GP is considered as both a generative and discriminative model. Furthermore, a fully variational Bayesian treatment for multiclass GP classification with multinomial probit likelihood is employed to estimate the hyperparameters and infer the predictive distributions. Simulation results on both synthetic data and a real world application of human action recognition in videos demonstrate the effectiveness and advantages of the proposed approach on classification of multiway tensor data, especially in the case that the underlying structure information among multimodes is discriminative for the classification task. 15:15 A Cyclic Weighted Median Method for L1 Low-Rank Matrix Factorization with Missing EntriesSPEAKER: unknownABSTRACT. A challenging problem in machine learning, information retrieval and computer vision research is how to recover a low-rank representation of the given data in the presence of outliers and missing entries. The L1-norm low-rank matrix factorization (LRMF) has been a popular approach to solving this problem. However, L1-norm LRMF is difficult to achieve due to its non-convexity and non-smoothness, and existing methods are often inefficient and fail to converge to a desired solution. In this paper we propose a novel cyclic weighted median (CWM) method, which is intrinsically a coordinate decent algorithm, for L1-norm LRMF. The CWM method minimizes the objective by solving a sequence of scalar minimization sub-problems, each of which is convex and can be easily solved by the weighted median filter. The extensive experimental results validate that the proposed CWM method outperforms state-of-the-arts in terms of both accuracy and computational efficiency. 15:30 Supervised Nonnegative Tensor Factorization with Maximum-Margin ConstraintSPEAKER: unknownABSTRACT. Non-negative tensor factorization (NTF) has attracted great attention in the machine learning community. In this paper, we extend traditional non-negative tensor factorization into a supervised discriminative decomposition, referred as Supervised Non-negative Tensor Factorization with Maximum-Margin constraints (SNTFM^2). SNTFM^2 formulates the optimal discriminative factorization of non-negative tensorial data as a coupled least-squares optimization problem via a maximum-margin method. As a result, SNTFM^2 not only faithfully approximates the tensorial data by additive combinations of the basis, but also obtains a strong generalization power to discriminative analysis (in particular for classification in this paper). The experimental results show the superiority of our proposed model over state-of-the-art techniques on both toy and real world data sets.
14:45-15:45 Session 27C: Equilibrium and Negotiation
 14:45 Efficient Evolutionary Dynamics with Extensive-Form GamesSPEAKER: unknownABSTRACT. Evolutionary game theory combines game theory and dynamical systems and is customarily adopted to describe evolutionary dynamics in multi-agent systems. In particular, it has been proven to be a successful tool to describe multi-agent learning dynamics. To the best of our knowledge, we provide in this paper the first replicator dynamics applicable to the sequence form of an extensive-form game, allowing an exponential reduction of time and space w.r.t. the currently adopted replicator dynamics for normal form. Furthermore, our replicator dynamics is realization equivalent to the standard replicator dynamics for normal form. We prove our results for both discrete-time and continuous-time cases. Finally, we extend standard tools to study the stability of a strategy profile to our replicator dynamics. 15:00 An Agent Design for Repeated Negotiation and Information Revelation with PeopleSPEAKER: unknownABSTRACT. Many negotiations in the real world are characterized by incomplete information, and participants' success depends on their ability to reveal information in a way that facilitates agreement without compromising their individual gains. This paper presents a novel agent design for repeated negotiation in incomplete information settings that learns to reveal information strategically during the negotiation process. The agent used classical machine learning techniques to predict how people make and respond to offers during the negotiation, how they reveal information, and their response to potential revelation actions by the agent. The agent was evaluated empirically in an extensive empirical study spanning hundreds of human subjects. Results show that the agent was able to outperform people. It learned to (1) make offers that were beneficial to people while not compromising its own benefit; (2) incrementally reveal information to people in a way that increased its expected performance. We also show the agent was successful in new settings without the need to acquire additional data. This work demonstrates the efficacy of combining machine learning with opponent modeling techniques towards the design of computer agents for negotiating with people in settings of incomplete information. 15:15 Algorithms for Strong Nash Equilibrium with More than Two AgentsSPEAKER: unknownABSTRACT. Strong Nash equilibrium (SNE) is an appealing solution concept when rational agents can form coalitions. A strategy profile is an SNE if no coalition of agents can benefit by deviating. An SNE must simultaneously be a Nash equilibrium (NE) and the optimal solution of multiple non-convex optimization problems. This makes even the derivation of necessary and sufficient equilibrium constraints in a mathematical programming fashion difficult. We show that forcing an SNE to be resilient only to pure strategy deviations by coalitions, unlike for NEs, is only a necessary condition here. Second, we show that the application of Karush-Kuhn-Tucker conditions leads to another set of necessary conditions that are not sufficient. Third, we show that forcing the Pareto efficiency of an SNE for each coalition with respect to coalition correlated strategies is sufficient but not necessary. We then develop a tree search algorithm for SNE finding. At each node, it calls an oracle to suggest a candidate SNE and then verifies the candidate. We show that our new necessary conditions can be leveraged to make the oracle more powerful. Experiments validate the overall approach and show that the new conditions significantly reduce search tree size compared to using NE conditions alone. 15:30 Equilibria of Online Scheduling AlgorithmsSPEAKER: Brendan LucierABSTRACT. We describe a model for competitive online scheduling algorithms. Two servers, each with a single observable queue, compete for customers. Upon arrival, each customer strategically chooses the queue with minimal expected wait time. Each scheduler wishes to maximize its number of customers, and can strategically select which scheduling algorithm, such as First-Come-First-Served (FCFS), to use for its queue. This induces a game played by the servers and the customers. We consider a non-Bayesian setting, where servers and customers play to maximize worst-case payoffs. We show that there is a unique subgame perfect safety-level equilibrium and we describe the associated scheduling algorithm (which is not FCFS). The uniqueness result holds for both randomized and deterministic algorithms, with a different equilibrium algorithm in each case. When the goal of the servers is to minimize competitive ratio, we prove that it is an equilibrium for each server to apply FCFS: each server obtains the optimal competitive ratio of 2.
14:45-15:45 Session 27D: Recommendation Systems
14:45-15:45 Session 27E: Human-Robot Collaboration
14:45-15:45 Session 27F: Spotlights and Senior Members
 14:45 ICWSM: What's Hot: Structure and Dynamics of Social Networks and Information NetworksSPEAKER: unknown 15:00 ICWSM: ChallengesSPEAKER: unknown 15:15 AAMAS: Best PaperSPEAKER: unknownABSTRACT. Piotr Krysta (University of Liverpool, Greece); Orestis Telelis (Athens University of Economics and Business, Greece); Carmine Ventre (Teesside University, UK) 15:30 AAMAS: What's HotSPEAKER: unknown
15:45-16:15Coffee Break
15:45-16:45 Session 28: LBP/Poster sessions
16:45-17:45 Session 29A: Reviewing
 16:45 Conference Reviewing: Best PracticesSPEAKER: Marie DesjardinsABSTRACT. Panel Organizers: Marie desJardins and Michael Littman Panelists: Ariel Felner, Kristian Kersting, Ashish Sabharwal This panel will focus on the reviewing process and best practices for reviewers, senior program committee members, and area/conference chairs. Topics will include how to write an effective review, the dynamics of reviewer discussions, handling author feedback, ethics of author/reviewer conflicts, and alternative reviewing models. The panel is for all AAAI community members but is particularly designed to help graduate students, postdocs, and junior faculty "learn the ropes" of the reviewing process. Relevant issues for these junior community members, such as "standing your ground" with more senior reviewers and how to "grow" into becoming a PC member or SPC, will be explored.
16:45-17:45 Session 29B: Planning Under Uncertainty
 16:45 Assumption-Based Planning: Generating Plans and Explanations under Incomplete KnowledgeSPEAKER: unknownABSTRACT. Many practical planning problems necessitate the generation of a plan under incomplete information about the state of the world. In this paper we propose the notion of Assumption-Based Planning. Unlike conformant planning, which attempts to find a plan under all possible completions of the initial state, an assumption-based plan supports the assertion of additional assumptions about the state of the world, simplifying the planning problem, and often resulting in high quality plans where no conformant plan exists. We are interested in this paradigm of planning for two reasons: 1) it captures a compelling form of commonsense planning, and 2) it is of great utility in the generation of explanations, diagnoses, and counter-examples -- tasks which share a computational core with planning. We formalize the notion of assumption-based planning, establishing a relationship between assumption-based and conformant planning, and prove properties of such plans. We further provide for the scenario where some assumptions are more preferred than others. Exploiting the correspondence with conformant planning, we propose a means of computing assumption-based plans via a translation to classical planning. Our translation is an extension of the popular approach proposed by Palacios and Geffner and realized in their T0 planner. We have implemented our planner, A0, as a variant of T0 and tested it on a number of expository domains drawn from the International Planning Competition. Our results illustrate the utility of this new planning paradigm. 17:00 A Fast Pairwise Heuristic for Planning under UncertaintySPEAKER: unknownABSTRACT. POMDP (Partially Observable Markov Decision Process) is a mathematical framework that models planning under uncertainty. Solving a POMDP is an intractable problem and even the state of the art POMDP solvers are too computationally expensive for large domains. This is a major bottleneck. In this paper, we propose a new heuristic, called the pairwise heuristic, that can be used in a one-step greedy strategy to find a near optimal solution for POMDP problems very quickly. This approach is a good candidate for large problems where real-time solution is a necessity but exact optimality of the solution is not vital. The pairwise heuristic uses the optimal solutions for pairs of states. For each pair of states in the POMDP, we find the optimal sequence of actions to resolve the uncertainty and to maximize the reward, given that the agent is uncertain about which state of the pair it is in. Then we use these sequences as a heuristic and find the optimal action in each step of the greedy strategy using this heuristic. We have tested our method on the available large classical test benchmarks in various domains. The resulting total reward is close to, if not greater than, the total reward obtained by other state of the art POMDP solvers, while the time required to find the solution is always much less. 17:15 Mixed Observability Predictive State RepresentationsSPEAKER: unknownABSTRACT. Learning accurate models of agent behaviours is crucial for the purpose of controlling multiagent systems where the agent and environment dynamics are unknown. Many multiagent systems exhibit mixed observability, where the multiple interacting agents are heterogenous - observations of some of the agents are essentially perfect and noiseless, while observations of other agents are imperfect, aliased or noisy. Predictive state representations are well-suited to model learning but had hitherto not been adapted to such systems. We present a new model learning framework, the mixed observability predictive state representation (MO-PSR), which exploits structural properties present in mixed observability multiagent systems to learn models that allow more efficient planning and control. We present a learning algorithm that is scalable to large amounts of data and to large mixed observability domains, and show theoretical analysis of the learning consistency and computational complexity. Empirical results demonstrate that our algorithm is capable of learning accurate models, at a larger scale than with the generic predictive state representation, by leveraging the mixed observability properties. 17:30 Qualitative Planning under Partial Observability in Multi-Agent DomainsSPEAKER: unknownABSTRACT. Decentralized POMDPs (Dec-POMDPs) provide a rich, attractive model for planning under uncertainty and partial observability in cooperative multi-agent domains with a growing body of research. In this paper we formulate a qualitative, propositional model for multi-agent planning under uncertainty with partial observability, which we call QDec-POMDP. We show that the worst-case complexity of planning in QDec-POMDPs is similar to that of Dec-POMDPs. Still, because the model is more "classical" in nature, it is more compact and easier to specify. Furthermore, it eases the adaptation of methods used in classical and contingent planning to solve problems to which Dec-POMDPs solution techniques cannot scale up. In particular, in this paper we describe a method based on compilation to classical planning, which handles multi-agent planning problems significantly larger than those handled by current Dec-POMDP algorithms.
16:45-17:45 Session 29C: Logic and Knowledge Representation