AAAI ON THURSDAY, JULY 18TH, 2013
View: session overviewtalk overviewside by side with other conferences
09:00 | AAAI-13 Invited Talk: Socially Assistive Robotics: Human-Robot Interaction Methods for Creating Robots That Care SPEAKER: Maja Mataric' ABSTRACT. Socially assistive robotics (SAR) is a new field of intelligent robotics that focuses on developing machines capable of assisting users through social rather than physical interaction. The robot's physical embodiment is at the heart of SAR's effectiveness, as it leverages the inherently human tendency to engage with lifelike (but not necessarily humanlike or otherwise biomimetic) social behavior. People readily ascribe intention, personality, and emotion to robots; SAR leverages this engagement stemming from non-contact social interaction involving speech, gesture, movement demonstration and imitation, and encouragement, to develop robots capable of monitoring, motivating, and sustaining user activities and improving human learning, training, performance and health outcomes. Human-robot interaction (HRI) for SAR is a growing multifaceted research area at the intersection of engineering, health sciences, neuroscience, social, and cognitive sciences. This talk will describe our research into embodiment, modeling and steering social dynamics, and long-term user adaptation for SAR. The research will be grounded in projects involving analysis of multi-modal activity data, modeling personality and engagement, formalizing social use of space and non-verbal communication, and personalizing the interaction with the user over a period of months, among others. The presented methods and algorithms will be validated on implemented SAR systems evaluated by human subject cohorts from a variety of user populations, including stroke patients, children with autism spectrum disorder, and elderly with Alzheimers and other forms of dementia. |
10:20 | Multi-Label Learning with PRO Loss SPEAKER: unknown ABSTRACT. Multi-label learning approaches assign multiple labels to one object. However, besides differentiating relevant labels from irrelevant ones, it is often required in real applications to rank the \textit{relevant} labels for an object, while the ranking of \textit{irrelevant} labels is not so valuable. Such a requirement, however, cannot be well satisfied by existing approaches. One crucial reason is that most approaches were designed to optimize existing criteria, yet there is no criterion which encodes the above requirement. In this paper, we design a new criterion, \textsf{PRO Loss}, which concerns about the prediction on all labels as well as the ranking of relevant labels, while neglecting the ranking of irrelevant ones. We then propose the ProSVM approach which optimizes the \textsf{PRO Loss} efficiently using alternating direction method of multipliers. We further improve efficiency with an upper approximation that reduces the number of constraints from $O(T^2)$ to $O(T)$, where $T$ is the number of labels. Experiments show that our proposals are not only superior to state-of-the-art approaches on \textsf{PRO Loss}, but also highly competitive on existing evaluation criteria. |
10:35 | Supervised Coupled Dictionary Learning with Group Structures for Multi-modal Retrieval SPEAKER: unknown ABSTRACT. A better similarity mapping function across heterogenous high-dimensional features is very desirable for many applications involving multi-modal data. In this paper, we introduce coupled dictionary learning (DL) into supervised sparse coding for multimodal retrieval. We call this Supervised coupled-dictionary learning with group structures for Multi-Modal retrieval(SliM^2). SliM^2 formulates the multi-modal metric learning as a constrained dictionary learning problem. By the utilization of intrinsic power of dealing with the heterogenous features in DL, SliM^2 first extends uni-modal DL to multi-modal DL. Moreover, the label information is employed in SliM^2 to discover the shared structure inside intra-modality within a same class by a mixed norm (i.e., l_1/ l_2 norm). At last, the multi-modal retrieval is conducted via a jointly learned mapping function across multi-modal data. The experimental results show the effectiveness of our proposed model when applied to multi-modal retrieval. |
10:50 | Convex Subspace Representation Learning from Multi-view Data SPEAKER: Yuhong Guo ABSTRACT. Learning from multi-view data is important in many applications. In this paper, we propose a novel convex subspace representation learning method for multi-view clustering. We first formulate the subspace learning in multiple views as one joint optimization problem with a common subspace representation matrix and a group sparsity inducing norm. By exploiting the properties of dual norms, we then show a convex min-max dual formulation with a sparsity inducing trace norm can be obtained. We develop a proximal bundle optimization algorithm to globally solve the min-max optimization problem. Our empirical study shows the proposed subspace representation learning can effectively facilitate the multi-view clustering task and outperform alternative multi-view clustering methods across different scenarios. |
11:05 | AAAI-13 Outstanding Paper Award: SMILe: Shuffled Multiple-Instance Learning SPEAKER: unknown ABSTRACT. Resampling techniques such as bagging are often used in supervised learning to produce more accurate classifiers. In this work, we show that multiple-instance learning admits a different form of resampling, which we call "shuffling." In shuffling, we resample instances in such a way that the resulting bags are likely to be correctly labeled. We show that resampling results in both a reduction of bag label noise and a propagation of additional informative constraints to a multiple-instance classifier. We empirically evaluate shuffling in the context of multiple-instance classification and multiple-instance active learning and show that the approach leads to significant improvements in accuracy. |
10:20 | Timelines with Temporal Uncertainty SPEAKER: unknown ABSTRACT. Timelines are a formalism to model planning domains where the temporal aspects are predominant, and have been used in many real-world applications. Despite their practical success, a major limitation is the inability to model temporal uncertainty, i.e. the fact that the plan executor cannot decide the actual duration of some activities. In this paper we make two key contributions. First, we propose a comprehensive, semantically well founded framework that (conservatively) extends with temporal uncertainty the state of the art timeline approach. Second, we focus on the problem of producing time-triggered plans that are robust with respect to temporal uncertainty, under a bounded horizon. In this setting, we present the first complete algorithm, and we show how it can be made practical by leveraging the power of Satisfiability Modulo Theories. |
10:35 | Decoupling the Multiagent Disjunctive Temporal Problem SPEAKER: unknown ABSTRACT. The Multiagent Disjunctive Temporal Problem (MaDTP) is a general constraint-based formulation for scheduling problems that involve interdependent agents. Decoupling agents' interdependent scheduling problems, so that each agent can manage its schedule independently, requires agents to adopt more restrictive local constraints that effectively subsume their interdependencies. In this paper, we present the first algorithms for decoupling MaDTPs. Our distributed algorithm is provably sound and complete. Our experiments demonstrate that the relative efficiency of finding a temporal decoupling improves with the interconnectedness between agents' schedules, leading to orders of magnitude speedup over algorithms that find complete solution spaces for MaDTPs. However, decoupling by its nature restricts agents' local scheduling flexibility; we define novel flexibility metrics for decoupled MaDTPs, and show empirically how the flexibility sacrificed depends on the degree of coupling between agents' schedules. |
10:50 | Temporal Milestones in HTNs SPEAKER: Brett Benyo ABSTRACT. We present temporal milestones for hierarchical task networks to enable the complex synchronization of tasks. A temporal milestone of a task is an intermediate event that occurs during the execution of a complex task, e.g., the start time, the end time or a milestone of any of its subtasks. Unlike landmark variables, introduced in existing work, temporal milestones respect the task abstraction boundaries and preserve structural properties enabling much more efficient reasoning. Furthermore, temporal milestones are expressive as landmark variables. We provide analytical and empirical evidence to support these claims. |
11:05 | Simple Temporal Problems with Taboo Regions SPEAKER: unknown ABSTRACT. In this paper, we define and study the general framework of Simple Temporal Problems with Taboo regions (STPTs), and we show how these problems capture metric temporal reasoning aspects which are common to many real-world applications. STPTs encode simple temporal constraints between events and user-defined taboo regions on the timeline during which no event is allowed to execute. We discuss two different variants of STPTs. The first one deals with instantaneous events, while the second one allows for processes with flexible durations. We also provide polynomial-time algorithms for solving them. When not all events or processes can be scheduled outside of the taboo regions, one needs to define and reason about "soft" STPTs. We show that even "soft" STPTs can be solved in polynomial time, using reductions to max-flow. This also allows for incremental computation, which is central to the successful application of our approach in real-time domains. |
10:20 | “Meeting the Responsibility to Explain AI” SPEAKER: unknown ABSTRACT. Every scientist and every scientific society has a responsibility to explain goals and methods and convey research results to the lay public, with additional importance attached to educating young students in science, technology, engineering, and mathematics. AITopics was set up to meet this responsibility for the AAAI and has been in operation for over ten years. We will describe some of the technical problems we face and describe opportunities for new technological development. |
10:50 | ICAPS: Best paper SPEAKER: Ron Petrick ABSTRACT. Ronald P. A. Petrick, Mary Ellen Foster Novel Applications track Best Paper: Planning for Social Interaction in a Robot Bartender Domain A robot coexisting with humans must not only be able to perform physical tasks, but must also be able to interact with humans in a socially appropriate manner. In many social settings, this involves the use of social signals like gaze, facial expression, and language. We describe an application of planning to task-based social interaction using a robot that must interact with multiple human agents in a simple bartending domain. Social states are inferred from low-level sensors, using vision and speech as input modalities. The knowledge-level PKS planner is used to construct plans with task, dialogue, and social actions, as an alternative to current mainstream approaches of interaction management. The resulting system has been tested with human users in a series of drink ordering scenarios. |
11:05 | ICAPS: What's Hot SPEAKER: unknown |
11:20 | Resolution and Parallelizability: Barriers to the Efficient Parallelization of SAT Solvers SPEAKER: unknown ABSTRACT. Recent attempts to create versions of Satisfiability (SAT) solvers that exploit parallel hardware have met with limited success. In fact, the most successful parallel solvers in recent competitions were based on portfolio approaches with little to no exchange of information between processors. This experience contradicts the apparent parallelizability of exploring a combinatorial search space. We present evidence that this discrepancy can be explained by studying SAT solvers as resolution refutation engines. Starting with the observation that a recently studied measure of resolution proofs, namely depth, provides a (weak) upper bound to the best possible speedup achievable by such solvers, we empirically show the existence of bottlenecks to parallelizability that refutations typically generated by SAT solvers exhibit. Further, we propose a new measure that explicitly accounts for a bounded number of parallel processors and empirically correlates with parallel speedups observed in practice. Our findings suggest that efficient parallelization of such solvers is not simply a matter of finding the right clause sharing heuristics, it is also hindered by the structure of the refutations these solvers produce. |
11:35 | Partial MUS Enumeration SPEAKER: Alessandro Previti ABSTRACT. Minimal explanations of infeasibility find a wide range of uses. In the Boolean domain, these are referred to as Minimal Unsatisfiable Subsets (MUSes). In some settings, one needs to enumerate MUSes of a Boolean formula. Most often the goal is to enumerate all MUSes. In cases where this is computationally infeasible, an alternative is to enumerate some MUSes. This paper develops a novel approach for partial enumeration of MUSes, that complements existing alternatives. If the enumeration of all MUSes is viable, then existing alternatives represent the best option. However, for formulas where the enumeration of all MUSes is unrealistic, our approach provides a solution for enumerating some MUSes within a given time bound. The experimental results focus on formulas for which existing solutions are unable to enumerate MUSes, and shows that the new approach can in most cases enumerate a non-negligible number of MUSes within a given time bound. |
11:50 | Greedy or Not? Best Improving versus First Improving Stochastic Local Search for MAXSAT SPEAKER: unknown ABSTRACT. Stochastic local search (SLS) is the dominant algorithmic paradigm for incomplete SAT and MAXSAT solvers. Early studies on small 3SAT instances found that the use of greedy improving moves did not improve search compared to using next improving moves (Gent and Walsh 1992, 1993). Yet several recent algorithms commonly have two modes: a greedy search followed by diversification (Tompkins, Balint and Hoos 2011). We revisit the early results by empirically studying the impact of greediness on SLS performance on much larger instances, including both random 3SAT and industrial MAXSAT problems. Current implementations using greedy moves tend to be much less efficient than using next improving moves. We implement an efficient buffering algorithm that makes greedy moves just as efficient as next improving moves. We compare versions of GSAT and AdaptG2WSAT using next and greedy moves for both finding the first optima and guiding local search during diversification. We find that the first local optima found using greedy moves are statistically significantly better than the first local optima found using next improving moves. However, this advantage reverses after subsequent search; given sufficient search time, solutions are significantly better most of the time when using next improving moves. For larger random as well as industrial MAXSAT problems, current algorithm design should revisit the use of next improving moves. |
12:05 | Improving WalkSAT for Random k-Satisfiability Problem with k>3 SPEAKER: unknown ABSTRACT. Stochastic local search (SLS) algorithms are well known for their ability to efficiently find models of randomly generated instances of the Boolean satisfiablity (SAT) problem. One of the most famous SLS algorithms for SAT is WalkSAT, which is an initial algorithm that has wide influence among modern SLS algorithms. Recently, there has been increasing interest in WalkSAT, due to the discovery of its great power on large random 3-SAT instances. However, the performance of WalkSAT on random $k$-SAT instances with $k>3$ lags far behind. Indeed, there have been few works in improving SLS algorithms for such instances. This work takes a first large step towards this direction. We propose a novel concept namely $multilevel$ $make$. Based on this concept, we design a scoring function called $linear$ $make$, which is utilized to break ties in WalkSAT, leading to a new algorithm called WalkSAT$lm$. Our experimental results on random 5-SAT and 7-SAT instances show that WalkSAT$lm$ improves WalkSAT by orders of magnitudes. Moreover, WalkSAT$lm$ significantly outperforms state-of-the-art SLS solvers on random 5-SAT instances, while competes well on random 7-SAT ones. Additionally, WalkSAT$lm$ performs very well on random instances from SAT Challenge 2012, indicating its robustness. |
11:20 | Introducing Nominals to the Combined Query Answering Approaches for EL SPEAKER: unknown ABSTRACT. So-called combined approaches answer a conjunctive query over a description logic ontology in three steps: first, they materialise certain consequences of the ontology and the data; second, they evaluate the query over the data; and third, they filter the result of the second phase to eliminate unsound answers. Such approaches were developed for various members of the DL-Lite and the $\mathcal{EL}$ families of languages, but none of them can handle ontologies containing nominals. In our work, we bridge this gap and present a combined query answering approach for $\mathcal{elho}^r_\bot$---a logic that contains all features of the OWL 2 EL standard apart from transitive roles and complex role inclusions; this is nontrivial because nominals require equality reasoning, which introduces complexity into the first and the third step. Our empirical evaluation suggests that our technique is suitable for practical application, and so it provides a practical basis for conjunctive query answering in a large fragment of OWL 2 EL. (with Boris Motik, Ian Horrocks, AIW-68) |
11:35 | Not Quite the Same: Identity Constraints for the Web of Linked Data SPEAKER: Gerard de Melo ABSTRACT. Linked Data is based on the idea that information from different sources can flexibly be connected to enable novel applications that individual datasets do not support on their own. This hinges upon the existence of links to connect datasets that would otherwise be isolated. The most notable form, sameAs links, are intended to express that two identifiers are equivalent in all respects. Unfortunately, many existing links do not reflect such genuine identity. This study provides a novel method to analyse this phenomenon, based on a thorough theoretical analysis, as well as a novel graph-based method to resolve such issues to some extent. Our experiments on a representative Web-scale set of sameAs links from the Web of Linked Data show that our method can identify and remove hundreds of thousands of constraint violations. |
13:45 | Model Predictive Control with Uncertainty in Human Driven Systems SPEAKER: unknown ABSTRACT. Human driven systems present a unique optimization challenge for robot control. Generally, operators of these systems behave rationally given environmental factors and desired goals. However, information available to subsystem controllers is often incomplete, and the operator becomes more difficult to model without this input information. In this work we present a data-driven, nonparametric model to capture both expectation and uncertainty of the upcoming duty for a subsystem controller. This model is a modified k-nearest neighbor regressor used to generate weighted samples from a distribution of upcoming duty, which are then exploited to generate an optimal control. We test the model on a simulated heterogeneous energy pack manager in an Electric Vehicle operated by a human driver. For this domain, upcoming load on the energy pack strongly affects the optimal use and charging strategy of the pack. Given incomplete information, there is a natural uncertainty in upcoming duty due to traffic, destination, signage, and other factors. We test against a dataset of real driving data gathered from volunteers, and compare the results other models and the optimal upper bound. |
14:00 | Negotiated Learning for Smart Grid Agents: Entity Selection Based on Dynamic Partially Observable Features SPEAKER: unknown ABSTRACT. An attractive approach to managing electricity demand in the Smart Grid relies on real-time pricing (RTP) tariffs, where customers are incentivized to quickly adapt to changes in the cost of supply. However, choosing amongst competitive RTP tariffs is difficult when tariff prices change rapidly. The problem is further complicated when we assume that the price changes for a tariff are published in real-time only to those customers who are currently subscribed to that tariff, thus making the prices partially observable. We present models and learning algorithms for autonomous agents that can address the tariff selection problem on behalf of customers. We introduce 'Negotiated Learning', a general algorithm that enables a self-interested sequential decision-making agent to periodically select amongst a variable set of 'entities' (e.g., tariffs) by negotiating with other agents in the environment to gather information about dynamic partially observable entity 'features' (e.g., tariff prices) that affect the entity selection decision. We also contribute a formulation of the tariff selection problem as a 'Negotiable Entity Selection Process', a novel representation. We support our contributions with intuitive justification and simulation experiments based on real data on an open Smart Grid simulation platform. |
14:15 | Autonomous Agents in Future Energy Markets: The 2012 Power Trading Agent Competition SPEAKER: unknown ABSTRACT. Sustainable energy systems of the future will need more than efficient, clean, and low-cost energy sources. They will also need efficient price signals that motivate sustainable energy consumption behaviors and a tight real-time alignment of energy demand with supply from renewable and traditional sources. The Power Trading Agent Competition (Power TAC) is a rich, competitive, open-source simulation platform for future retail power markets built on real-world data and state-of-the-art customer models. Its purpose is to help researchers understand the dynamics of customer and retailer decision-making as well as the robustness of proposed market designs. Power TAC invites researchers to develop electricity broker agents and benchmark them against the best-performing strategies from leading energy market researchers worldwide. This provides compelling, actionable information for policy makers and industry leaders. We describe the competition scenario, demonstrate the realism of the Power TAC platform, and analyze key characteristics of successful brokers in one of our 2012 pilot competitions between seven research groups from five different countries. |
14:30 | Large Landscape Conservation—Synthetic and Real-world Datasets SPEAKER: Carla Gomes ABSTRACT. Biodiversity underpins ecosystem goods and services and hence protecting it is key to achieving sustainability. However, the persistence of many species is threatened by habitat loss and fragmentation due to human land use and climate change. Conservation efforts are implemented under very limited economic resources, and therefore designing scalable, cost-efficient and systematic approaches for conservation planning is an important and challenging computational task. In particular, preserving landscape connectivity between good habitat has become a key conservation priority in recent years. We give an overview of landscape connectivity conservation and some of the underlying graph-theoretic optimization problems. We present a synthetic generator capable of creating families of randomized structured problems, capturing the essential features of real-world instances but allowing for a thorough typical-case performance evaluation of different solution methods. We also present two large-scale real-world datasets, including economic data on land cost, and species data for grizzly bears, wolverines and lynx. |
13:45 | Supervised and Projected Sparse Coding for Image Classification SPEAKER: unknown ABSTRACT. Classic sparse representation for classification (SRC) method fails to incorporate the label information of training images, and meanwhile has a poor scalability due to the expensive computation for L1 norm. In this paper, we propose a novel subspace sparse coding method with utilizing label information to effectively classify the images in the subspace. Our new approach unifies the tasks of dimension reduction and supervised sparse vector learning, by simultaneously preserving the data sparse structure and meanwhile seeking the optimal projection direction in the training stage, therefore accelerates the classification process in the test stage. Our method achieves both flat and structured sparsity for the vector representations, therefore making our framework more discriminative during the subspace learning and subsequent classification. The empirical results on 4 benchmark data sets demonstrate the effectiveness of our method. |
14:00 | Joint Object and Pose Recognition Using Homeomorphic Manifold Analysis SPEAKER: Haopeng Zhang ABSTRACT. Object recognition is a key precursing challenge in the fields of object manipulation and robotic/AI reasoning in general. Recognizing object categories, particular instances of objects and viewpoints/poses of objects are three critical subproblems robots must solve in order to accurately grasp/manipulate objects and reason about their environments. Multi-view images of the same object lie on intrinsic low-dimensional manifolds in descriptor spaces (e.g. visual/depth descriptor spaces). These object manifolds share the same topology despite being geometrically different. Each object manifold can be represented as a deformed version of a unified manifold. The object manifolds can thus be parametrized by its homeomorphic mapping/reconstruction from the unified manifold. In this work, we construct a manifold descriptor from this mapping between homeomorphic manifolds and use it to jointly solve the three challenging recognition sub-problems. We extensively experiment on a challenging multi-modal (i.e. RGBD) dataset and other object pose datasets and achieve state-of-the-art results. |
14:15 | Vector-Valued Multi-View Semi-Supervised Learning for Multi-Label Image Classification SPEAKER: Chao Xu ABSTRACT. Images are usually associated with multiple labels and comprised of multiple views, due to each image containing several objects (e.g. a pedestrian, bicycle and tree) and multiple visual features (e.g. color, texture and shape). Currently available tools tend to use either labels or features for classification, but both are necessary to describe the image properly. There have been recent successes in using vector-valued functions, which construct matrix-valued kernels, to explore the multi-label structure in the output space. This has motivated us to develop multi-view vector-valued manifold regularization (MV$^3$MR) in order to integrate multiple features. MV$^3$MR exploits the complementary properties of different features, and discovers the intrinsic local geometry of the compact support shared by different features, under the theme of manifold regularization. We validate the effectiveness of the proposed MV$^3$MR methodology for image classification by conducting extensive experiments on two challenge datasets, PASCAL VOC' 07 and MIR Flickr. |
13:45 | GiSS: Combining Gibbs Sampling and SampleSearch for Inference in Mixed Probabilistic and Deterministic Graphical Models SPEAKER: unknown ABSTRACT. Mixed probabilistic and deterministic graphical models are ubiquitous in real-world applications. Unfortunately, Gibbs sampling, a popular MCMC technique, does not converge to the correct answers in presence of determinism and therefore cannot be used for inference in such models. In this paper, we propose to remedy this problem by combining Gibbs sampling with SampleSearch, an advanced importance sampling technique which leverages complete SAT/CSP solvers to generate high quality samples from hard deterministic spaces. We call the resulting algorithm, GiSS. Unlike Gibbs sampling which yields unweighted samples, GiSS yields weighted samples. Computing these weights exactly can be computationally expensive and therefore we propose several approximations. We show that our new weighting schemes yield consistent estimates and demonstrate experimentally that GiSS is competitive in terms of accuracy with state-of-the-art approximate inference algorithms such as SampleSearch, MC-SAT and Belief propagation. |
14:00 | Complexity of Inferences in Polytree-shaped Semi-Qualitative Probabilistic Networks SPEAKER: Cassio De Campos ABSTRACT. Semi-qualitative probabilistic networks (SQPNs) merge two important graphical model formalisms: Bayesian networks and qualitative probabilistic networks. They provide a very general modeling framework by allowing the combination of numeric and qualitative assessments over a discrete domain, and can be compactly encoded by exploiting the same factorization of joint probability distributions that are behind the Bayesian networks. This paper explores the computational complexity of semi-qualitative probabilistic networks, and takes the polytree-shaped networks as its main target. We show that the inference problem is coNP-Complete for binary polytrees with multiple observed nodes. We also show that inferences can be performed in linear time if there is a single observed node, which is a relevant practical case. Because our proof is constructive, we obtain an efficient linear time algorithm for SQPNs under such assumptions. To the best of our knowledge, this is the first exact polynomial-time algorithm for SQPNs. Together these results provide a clear picture of the inferential complexity in polytree-shaped SQPNs. |
14:15 | Joint Extraction and Labeling via Graph Propagation for Dictionary Construction SPEAKER: unknown ABSTRACT. In this paper, we present an approach that jointly infers the boundaries of tokens and their labels to construct dictionaries for Information Extraction (IE). Our approach for joint-inference is based on a graph propagation framework, and extends it in two novel ways. First, we extend the graph representation to capture ambiguities that occur during the token extraction phase. Second, we modify the labeling phase (i.e. label propagation) to utilize this new representation, allowing evidence from labeling to be used for token extraction. Our evaluation shows these extensions (and hence our approach) significantly improve the performance of the outcome dictionaries over pipeline-based approaches by preventing aggressive commitment. Our evaluation also shows that our extensions over a base graph-propagation framework was able to improve the precision without hurting the recall. |
13:45 | Active Task Selection for Lifelong Machine Learning SPEAKER: unknown ABSTRACT. In a lifelong learning framework, an agent acquires knowledge incrementally over consecutive learning tasks, continually building upon its experience. Recent lifelong learning algorithms have achieved nearly identical performance to batch multi-task learning methods while requiring over three orders of magnitude less time to learn. In this paper, we further improve the scalability of lifelong learning by developing curriculum selection methods that enable an agent to actively select the next task to learn in order to maximize performance on future learning tasks. We demonstrate that active task selection is highly reliable and effective, allowing an agent to learn high performance models using up to 50% fewer tasks than when the agent has no control over the task order. We also explore a variant of transfer learning in the lifelong learning setting in which the agent can focus knowledge acquisition toward a particular target task, enabling the agent to quickly learn the target task. |
14:00 | Learning Integrated Symbolic and Continuous Action Models for Continuous Domains SPEAKER: unknown ABSTRACT. Long-living autonomous agents must be able to learn to perform competently in novel environments. One important aspect of competence is the ability to plan, which entails the ability to learn models of the agent’s own actions and their effects on the environment. In this paper we describe an approach to learn action models of environments with continuous-valued spatial states and realistic physics consisting of multiple interacting rigid objects. In such environments, we hypothesize that objects exhibit multiple qualitatively distinct behaviors we call modes, conditioned on their spatial relationships to each other. We argue that action models that explicitly represent these modes using a combination of symbolic spatial relationships and continuous metric information learn faster, generalize better, and make more accurate predictions than models that use only metric information. We present a method to learn action models with piecewise linear modes conditioned on a combination of first-order Horn clauses composed of symbolic spatial predicates and continuous classifiers. We empirically demonstrate with lesion studies in a physics simulation that our method learns more accurate and more general models than a method that learns a single smooth function (locally weighted regression) and a method that learns piecewise smooth functions not conditioned on spatial predicates. |
14:15 | Sparse Multi-task Learning for Detecting Influential Nodes in an Implicit Diffusion Network SPEAKER: Yingze Wang ABSTRACT. How to identify influential nodes is a central research topic in information diffusion analysis. Many existing methods rely on the assumption that the network structure is completely known by the model. However, in many applications, such a network is either unavailable or insufficient to explain the underlying information diffusion phenomena. To address this challenge, we develop a multi-task sparse linear influence model (MSLIM), which can simultaneously predict the volume for each contagion and automatically identify sets of the most influential nodes for different contagions. Our method is based on the linear influence model with two main advantages: 1) it does not require the network structure; 2) it can detect different sets of the most influential nodes for different contagions. To solve the corresponding convex optimization problem for learning the model, we adopt the accelerated gradient descent (AGM) framework and show that there is an exact closed-form solution for the proximal mapping. Therefore, the optimization procedure achieves the optimal first-order convergence rate and can be scaled to very large datasets. The proposed model is validated on a set of 2.6 millions of tweets of 1000 users on twitter. We show that MSLIM can efficiently select the most influential users for specific contagions. We also present several interesting patterns of the selected influential users. |
14:30 | Multiagent Learning with a Noisy Global Reward Signal SPEAKER: unknown ABSTRACT. Scaling multiagent reinforcement learning to domains with many agents is a complex problem. In particular, multiagent credit assignment becomes a key issue as the system size increases. Some multiagent systems suffer from a global reward signal that is very noisy or difficult to analyze. This makes deriving a learnable local reward signal very difficult. Difference rewards (a particular instance of reward shaping) have been used to alleviate this concern, but they remain difficult to compute in many domains. In this paper we present an approach to modeling the global reward using function approximation that allows the quick computation of local rewards. We demonstrate how this model can result in significant improvements in behavior for three congestion problems: a multiagent ``bar problem'', a complex simulation of the United States airspace, and a generic air traffic domain. We show how the model of the global reward may be either learned on- or off-line using either linear functions or neural networks. For the bar problem, we show an increase in reward of nearly 200% over learning using the global reward directly. For the air traffic problem, we show a decrease in costs of 25% over learning using the global reward directly. |
14:45 | Enabling E-Mobility: Facility Location for Battery Loading Stations SPEAKER: unknown ABSTRACT. The short cruising range due to the limited battery supply of current Electric Vehicles (EVs) is one of the main challenges to deal with to facilitate the transition to E-mobility. Until batteries of higher enery storage density have been developed, it is of utmost importance to deliberately plan the locations of new loading stations for best possible coverage. Ideally the network of loading stations should allow driving from anywhere to anywhere (and back) without running out of energy. More formally, given a street network with n nodes, we prove that achieving this goal with a minimal number of LSs is NP-hard to approximate within c ln n for c < 1 via reduction from the Dominating Set problem. On the positive side, we show with instance based lower bounds that even heuristics with incomplete knowledge achieve good solutions in practice. |
15:00 | Robust Network Design for Multispecies Conservation SPEAKER: Carla Gomes ABSTRACT. Our work is motivated by an important network design application in computational sustainability concerning wildlife conservation. In the face of human development and climate change, it is important that conservation plans for protecting landscape connectivity exhibit certain level of robustness. While previous work has focused on conservation strategies that result in a connected network of habitat reserves, the robustness of the proposed solutions has not been taken into account. In order to address this important aspect, we formalize the problem as a node-weighted bi-criteria network design problem with connectivity requirements on the number of disjoint paths between pairs of nodes. While in most previous work on survivable network design the objective is to minimize the cost of the selected network, our goal is to optimize the quality of the selected paths within a specified budget, while meeting the connectivity requirements. We characterize the complexity of the problem under different restrictions. We provide a mixed-integer programming encoding that allows for finding solutions with optimality guarantees, as well as a hybrid local search method with better scaling behavior but no guarantees. We evaluate the typical-case performance of our approaches using a synthetic benchmark, and apply them to a large-scale real-world network design problem concerning the conservation of wolverine and lynx populations in the U.S. Rocky Mountains (Montana). |
15:15 | Resource Sharing for Control of Wildland Fires SPEAKER: unknown ABSTRACT. Wildland fires (or wildfires) occur on all continents except for Antarctica. These fires threaten communities, change ecosystems and destroy vast amounts of natural resources, and the cost estimates of the damage done annually is in the billions of dollars. Controlling wildland fires is resource-intensive and there are numerous examples where resource demand has outstripped resource availability. Trends in changing climates, fire occurrence and expansion of the wildland-urban interface all point to increased resource shortages in the future. One approach for coping with these shortages has been the sharing of resources across different wildland-fire agencies. This introduces new issues as agencies have to balance their own needs and risk-management with their desire to help fellow agencies in need. Using ideas from the field of multiagent systems, we conduct the first analysis of strategic issues arising in resource-sharing for wildland-fire control, and highlight the importance in having clear protocols when allocating the resources. We also argue that the wildland-fire domain has numerous features that make it attractive to researchers in artificial intelligence and computational sustainability. |
15:30 | Multiagent Coordination for Energy Consumption Scheduling in Consumer Cooperatives SPEAKER: unknown ABSTRACT. A key challenge to create a sustainable and energy-efficient society is in making consumer demand adaptive to energy supply, especially renewable supply. In this paper, we propose a partially-centralized organization of consumers, namely, a consumer cooperative for purchasing electricity from the market. We propose a novel multiagent coordination algorithm to shape the energy consumption of the cooperative. In the cooperative, a central coordinator buys the electricity for the whole group and consumers make their own consumption decisions based on their private consumption constraints and preferences. To coordinate individual consumers under incomplete information, we propose an iterative algorithm in which a virtual price signal is sent by the coordinator to induce consumers to shift demand. We prove that our algorithm converges to the central optimal solution. Additionally we analyze the convergence rate of the algorithm via simulations using random instances. The results indicate that our algorithm is scalable with respect to the number of agents and consumption slots. |
14:45 | Optimizing Objective Function Parameters for Strength in Computer Game-Playing SPEAKER: unknown ABSTRACT. The learning of evaluation functions from game records has been widely studied in the field of computer game-playing. Conventional learning methods optimize the evaluation function parameters by using the game records of expert players in order to imitate their plays. They utilize objective functions to increase the agreement between the moves selected by game-playing programs and the moves in the records of actual games. Such conventional methods, however, have a problem in that increasing this agreement does not always improve the strength of the program. Indeed, it is not clear how the agreement relates to the strength of the generated program. To address this problem, this paper presents a learning method to optimize objective function parameters for strength of playing. The proposed method employs an evolutionary learning algorithm with the Elo ratings of programs, which denote the strength, as their fitness scores. Experimental results show that the proposed method is effective and that programs that learn using the objective function produced by the proposed method are superior to those that learn using conventional objective functions. |
15:00 | Filtering with Logic Programs and its Application to General Game Playing SPEAKER: Michael Thielscher ABSTRACT. Motivated by the problem of building a basic reasoner for general game playing with imperfect information, we address the problem of filtering with logic programs, whereby an agent updates its incomplete knowledge of a program by observations. We develop a filtering method by adapting an existing backward-chaining and abduction method for so-called open logic programs. Experimental results show that this provides for a basic effective and efficient "legal" player for general imperfect-information games. |
15:15 | Parameterized Complexity Results for Plan Reuse SPEAKER: unknown ABSTRACT. Planning is a notoriously difficult computational problem of high worst-case complexity. Researchers have been investing significant efforts to develop heuristics or restrictions to make planning practically feasible. Case-based planning is a heuristic approach where one tries to reuse previous experience when solving similar problems in order to avoid some of the planning effort. Plan reuse may offer an interesting alternative to plan generation in some settings. We provide theoretical results that identify situations in which plan reuse is provably tractable. We perform our analysis in the framework of parameterized complexity, which supports a rigorous worst-case complexity analysis that takes structural properties of the input into account in terms of parameters. A central notion of parameterized complexity is fixed-parameter tractability which extends the classical notion of polynomial-time tractability by utilizing the effect of structural properties of the problem input. We draw a detailed map of the parameterized complexity landscape of several variants of problems that arise in the context of case-based planning. In particular, we consider the problem of reusing an existing plan, imposing various restrictions in terms of parameters, such as the number of steps that can be added to the existing plan to turn it into a solution of the planning instance at hand. |
14:45 | How can AI help Synthetic Biology? SPEAKER: Aaron Adler ABSTRACT. Our primary goal in this talk is to draw the attention of the AI community to a novel and rich application domain, namely Synthetic Biology. Synthetic biology is the systematic design and engineering of biological systems. Synthetic organisms are currently designed at the DNA level, which limits the complexity of the systems. In our talk we will introduce the domain, describe the current workflow used by synthetic biologists, and demonstrate the feasibility of progress in this domain. Problems specific to each AI topic area will be highlighted. |
15:15 | ISWC: What's Hot, Challenges: Diagnosing Road Traffic Congestions in the Semantic Web SPEAKER: Anika Schumann |