Personal
On-Line Reconfigurable Machines
Crawford, Lara S. (Palo Alto Research Center (PARC)) | Do, Minh Binh (Palo Alto Research Center (PARC)) | Ruml, Wheeler S. (University of New Hampshire) | Hindi, Haitham (Accuray, Inc.) | Eldershaw, Craig (Palo Alto Research Center (PARC)) | Zhou, Rong (Palo Alto Research Center (PARC)) | Kuhn, Lukas (Qualcomm R&D) | Fromherz, Markus P. J. (Xerox) | Biegelsen, David (Palo Alto Research Center (PARC)) | Kleer, Johan de (Palo Alto Research Center (PARC)) | Larner, Daniel (Google)
We believe that these goals can be attained through the use of a very high level of modularity, both in hardware and software, combined with intelligent software. To test this hypothesis, Palo Alto Research Center (PARC) designed and built a prototype highly modular system in the printing domain. This "hypermodular" printer explores the extremes of modularity, reconfigurability, and parallelism in both hardware and software. The hardware prototype connects four standard Xerox marking engines (the component of a printer that does the actual printing) in parallel using a highly modular paper path. This configuration can achieve a print rate of four times that of an individual print engine. Reconfigurable manufacturing systems supports flexibility in configuration, graceful degradation (RMSs) were introduced as a concept in the late under component failure, and rerouting of inprocess 1990s (Koren et al. 1999), but the prerequisites, in sheets under exception conditions. These both software and hardware, for implementing them capabilities were made possible by utilizing advanced successfully have proved daunting; very few examples AI techniques in model-based planning, scheduling, of RMSs exist today in practice. These prerequisites search, and temporal reasoning such as state-space include modular, reconfigurable hardware components regression planning, partial-order scheduling, temporal as well as the software and control planning graph-based heuristic estimates, multiobjective architectures and logic to support them. RMSs can search, and fast, simple temporal network include both hard reconfigurability (physical reconfiguration) reasoning. The AI planner / scheduler incorporates and soft reconfigurability (logical reconfiguration) mostly domain-independent techniques from the (ElMaraghy 2006). This latter concept planning and scheduling research community, includes the idea of flexible routing as well as replanning enabling its flexibility and configurability to be and rescheduling.
Invited Talks
Hamilton, Carol (Association for the Advancement of Artificial Intelligence)
Most approaches to semantics in computational linguistics represent meaning in terms of words or abstract symbols. Grounded-language research bases the meaning of natural language on perception and/or action in the (real or virtual) world. Machine learning has become the most effective approach to constructing natural-language systems; however, current methods require a great deal of laboriously annotated training data. Ideally, a computer would be able to acquire language like a child, by being exposed to language in the context of a relevant but ambiguous environment, thereby grounding its learning in perception and action. We will review recent research in grounded language learning and discuss future directions.
A Concise Introduction to Models and Methods for Automated Planning
Planning is the model-based approach to autonomous behavior where the agent behavior is derived automatically from a model of the actions, sensors, and goals. The main challenges in planning are computational as all models, whether featuring uncertainty and feedback or not, are intractable in the worst case when represented in compact form. In this book, we look at a variety of models used in AI planning, and at the methods that have been developed for solving them. The goal is to provide a modern and coherent view of planning that is precise, concise, and mostly self-contained, without being shallow. For this, we make no attempt at covering the whole variety of planning approaches, ideas, and applications, and focus on the essentials.
Spherical perceptron as a storage memory with limited errors
It has been known for a long time that the classical spherical perceptrons can be used as storage memories. Seminal work of Gardner, \cite{Gar88}, started an analytical study of perceptrons storage abilities. Many of the Gardner's predictions obtained through statistical mechanics tools have been rigorously justified. Among the most important ones are of course the storage capacities. The first rigorous confirmations were obtained in \cite{SchTir02,SchTir03} for the storage capacity of the so-called positive spherical perceptron. These were later reestablished in \cite{TalBook} and a bit more recently in \cite{StojnicGardGen13}. In this paper we consider a variant of the spherical perceptron that operates as a storage memory but allows for a certain fraction of errors. In Gardner's original work the statistical mechanics predictions in this directions were presented sa well. Here, through a mathematically rigorous analysis, we confirm that the Gardner's predictions in this direction are in fact provable upper bounds on the true values of the storage capacity. Moreover, we then present a mechanism that can be used to lower these bounds. Numerical results that we present indicate that the Garnder's storage capacity predictions may, in a fairly wide range of parameters, be not that far away from the true values.
A Real-Time Decision Support System for High Cost Oil-Well Drilling Operations
Gundersen, Odd Erik (http://www.verdandetechnology.com) | Sørmo, Frode (Verdande Technology) | Aamodt, Agnar (Norwegian Unversity of Science and Technology) | Skalle, Pål (Norwegian University of Science and Technology)
In this article we present DrillEdge — a commercial and award winning software system that monitors oil-well drilling operations in order to reduce non-productive time (NPT). DrillEdge utilizes case-based reasoning with temporal representations on streaming real-time data, pattern matching and agent systems to predict problems and give advice on how to mitigate the problems. The methods utilized, the architecture, the GUI and development cost in addition to two case studies are documented.
PROTECT -- A Deployed Game Theoretic System for Strategic Security Allocation for the United States Coast Guard
An, Bo (University of Southern California) | Shieh, Eric (University of Southern California) | Tambe, Milind (University of Southern California) | Yang, Rong (University of Southern California) | Baldwin, Craig (United States Coast Guard) | DiRenzo, Joseph (United States Coast Guard) | Maule, Ben (United States Coast Guard) | Meyer, Garrett (United States Coast Guard)
While three deployed applications of game theory for security have recently been reported, we as a community of agents and AI researchers remain in the early stages of these deployments; there is a continuing need to understand the core principles for innovative security applications of game theory. Towards that end, this paper presents PROTECT, a game-theoretic system deployed by the United States Coast Guard (USCG) in the port of Boston for scheduling their patrols. USCG has termed the deployment of PROTECT in Boston a success, and efforts are underway to test it in the port of New York, with the potential for nationwide deployment.PROTECT is premised on an attacker-defender Stackelberg game model and offers five key innovations. First, this system is a departure from the assumption of perfect adversary rationality noted in previous work, relying instead on a quantal response (QR) model of the adversary's behavior --- to the best of our knowledge, this is the first real-world deployment of the QR model. Second, to improve PROTECT's efficiency, we generate a compact representation of the defender's strategy space, exploiting equivalence and dominance. Third, we show how to practically model a real maritime patrolling problem as a Stackelberg game. Fourth, our experimental results illustrate that PROTECT's QR model more robustly handles real-world uncertainties than a perfect rationality model. Finally, in evaluating PROTECT, this paper for the first time provides real-world data: (i) comparison of human-generated vs PROTECT security schedules, and (ii) results from an Adversarial Perspective Team's (human mock attackers) analysis.
TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems Using Game Theory
Yin, Zhengyu (University of Southern California) | Jiang, Albert Xin (University of Southern California) | Tambe, Milind (University of Southern California) | Kiekintveld, Christopher (University of Texas at El Paso) | Leyton-Brown, Kevin (University of British Columbia) | Sandholm, Tuomas (Carnegie Mellon University) | Sullivan, John P. (Los Angeles County Sheriff's Department)
In proof-of-payment transit systems, passengers are legally required to purchase tickets before entering but are not physically forced to do so. Instead, patrol units move about the transit system, inspecting the tickets of passengers, who face fines if caught fare evading. The deterrence of fare evasion depends on the unpredictability and effectiveness of the patrols. In this paper, we present TRUSTS, an application for scheduling randomized patrols for fare inspection in transit systems. TRUSTS models the problem of computing patrol strategies as a leader-follower Stackelberg game where the objective is to deter fare evasion and hence maximize revenue. This problem differs from previously studied Stackelberg settings in that the leader strategies must satisfy massive temporal and spatial constraints; moreover, unlike in these counterterrorism-motivated Stackelberg applications, a large fraction of the ridership might realistically consider fare evasion, and so the number of followers is potentially huge. A third key novelty in our work is deliberate simplification of leader strategies to make patrols easier to be executed. We present an efficient algorithm for computing such patrol strategies and present experimental results using real-world ridership data from the Los Angeles Metro Rail system. The Los Angeles County Sheriff’s department is currently carrying out trials of TRUSTS.