| All publications sorted by year |
| 2009 |
| 2008 |
| 2007 |
| Abstract: | "Abstract We present a goal-directed E-unification procedure with eager Variable Elimination and a new rule, Cycle, for the case of collapsing equations – that is, equations of the type x ≈ v where x ∈Var(v). Cycle replaces Variable Decomposition (or the so-called Root Imitation) and thus removes possibility of some obviously unnecessary infinite paths of inferences in the E-unification procedure. We prove that, as in other approaches, such inferences into variable positions in our goal-directed procedure are not needed. Our system is independent of selection rule and complete for any E-unification problem." |
| 2006 |
| Abstract: | "computational complexity, honours reading" |
| 2005 |
| Abstract: | "Multi-Agent Programming is an essential reference for anyone interested in the most up-to-date developments in MAS programming. While previous research has focused on the development of formal and informal approaches to analyze and specify Multi-Agent Systems, this book focuses on the development of programming languages and tools which not only support MAS programming, but also implement key concepts of MAS in a unified framework. Part I describes approaches that rely on computational logic or process algebra – Jason, 3APL, IMPACT, and CLAIM/SyMPA. Part II presents languages and platforms that extend or are based on Java – JADE, Jadex and JACKTM. Part III provides two significant industry specific applications – The DEFACTO System for coordinating human-agent teams for disaster response, and the ARTIMIS rational dialogue agent technology. Also featured are seven appendices for quick reference and comparison. Preface.- Foreword.- Acknowledgments.- Part I: Logic or Process Algebra-based Programming Languages.- Jason and the Golden Fleece of Agent-Oriented Programming.- Programming Multi-Agent Systems in 3APL 39.- IMPACT: A Multi-Agent Framework with Declarative Semantics.- CLAIM and SyMPA: A Programming Environment for Intelligent and Mobile Agents.- Part II: Java-Based Agent Programming Languages.- JADE: A Java Agent Development Framework.- Jadex: A BDI Reasoning Engine.- JACKTM Intelligent Agents: An Industrial Strength Platform.- Part III: Industrial-Strength Applications.- The DEFACTO System: Coordinating Human-Agent Teams for the Future of Disaster Response.- ARTIMIS Rational Dialogue Agent Technology.- Summaries for Quick Reference and Comparison.- Appendix A: Comparison Criteria.- Appendix B: Jason Summary.- Appendix C: 3APL Summary.- Appendix D: IMPACT Summary.- Appendix E: CLAIM Summary.- Appendix F: JADE Summary.- Appendix G: Jadex Summary.- Appendix H: JACK Summary.- References.- Index." |
| Abstract: | "Part I Effects of Scaling Coordination: The Effects of Locality and Asymmetry in Large-Scale Multiagent MDPs.- A Study of Scalability Properties in Robotic Teams.- Comparing Three Approaches to Large-Scale Coordination.- Part II Scaling Existing Coordination Approaches: Decentralized Partner Finding in Multi-Agent Systems.- Distributed Coordination of an Agent Society Based on Obligations and Commitments to Negotiated Agreements.- A Family of Graphical-Game-Based Algorithms for Distributed Constraint Optimization Problems.- Key-Based Coordination Strategies: Scalability Issues.- Designing Agent Utilities for Coordinated, Scalable and Robust Multi-Agent Systems.- Part III New Approaches for Large Scale Coordination: Learning Scalable Coaltion Formation in an Organizational Content.- Multi-Agent Coordination in Open Environments.- Mobile Agents.- WIZER: Automated Model Improvement in Multi-Agent Social-Network Systems.- Part IV Robustness and Flexibility in Large-Scale Multi-Agent Systems: Towards Flexible Coordination of Large Scale Multi-Agent Teams.- Techniques for Robust Planning in Degradable Multiagent Systems." |
| Abstract: | "We discuss the design of an acquisitional query processor for data collection in sensor networks. Acquisitional issues are those that pertain to where, when, and how often data is physically acquired (sampled) and delivered to query processing operators. By focusing on the locations and costs of acquiring data, we are able to significantly reduce power consumption over traditional passive systems that assume the a priori existence of data. We discuss simple extensions to SQL for controlling data acquisition, and show how acquisitional issues influence query optimization, dissemination, and execution. We evaluate these issues in the context of TinyDB, a distributed query processor for smart sensor devices, and show how acquisitional techniques can provide significant reductions in power consumption on our sensor devices." |
| Abstract: | "Accurate and low-cost sensor localization is a critical requirement for the deployment of wireless sensor networks in a wide variety of applications. Low-power wireless sensors may be many hops away from any other sensors with a priori location information. In cooperative localization, sensors work together in a peer-to-peer manner to make measurements and then form a map of the network. Various application requirements (such as scalability, energy efficiency, and accuracy) will influence the design of sensor localization systems. In this article, we describe measurement-based statistical models useful to describe time-of-arrival (TOA), angle-of-arrival (AOA), and received-signal-strength (RSS) measurements in wireless sensor networks. Wideband and ultra-wideband (UWB) measurements, and RF and acoustic media are also discussed. Using the models, we show how to calculate a Cramér-Rao bound (CRB) on the location estimation precision possible for a given set of measurements. This is a useful tool to help system designers and researchers select measurement technologies and evaluate localization algorithms. We also briefly survey a large and growing body of sensor localization algorithms. This article is intended to emphasize the basic statistical signal processing background necessary to understand the state-of-the-art and to make progress in the new and largely open areas of sensor network localization research." |
| Abstract: | "Similarly to human organizations, where the environment plays a fundamental role in supporting social activities, the environment of a multi-agent system (MAS) is the natural place where understanding and designing agent coordination. Accordingly, we propose the notion of coordination artifact as a unifying abstraction for engineering environment-based coordination of agents. This is meant to capture at the MAS level abstractions and concepts like services, tools, and artifacts, which are typically shared and exploited by the collectivity of individuals for achieving individual as well as global objectives. In this work we describe this framework, by defining a model for the coordination artifact abstraction, and discussing the infrastructures and technologies currently available for engineering MAS applications with coordination artifacts." |
| Abstract: | "FLUX is a programming method for the design of agents that reason logically about their actions and sensor information in the presence of incomplete knowledge. The core of FLUX is a system of Constraint Handling Rules, which enables agents to maintain an internal model of their environment by which they control their own behavior. The general action representation formalism of the fluent calculus provides the formal semantics for the constraint solver. FLUX exhibits excellent computational behavior due to both a carefully restricted expressiveness and the inference paradigm of progression." |
| Abstract: | "In a recent paper, we presented a new logic called ES for reasoning about the knowledge, action, and perception of an agent. Although formulated using modal operators, we argued that the language was in fact a dialect of the situation calculus but with the situation terms suppressed. This allowed us to develop a clean and workable semantics for the language without piggybacking on the generic Tarski semantics for first-order logic. In this paper, we reconsider the relation between ES and the situation calculus and show how to map sentences of ES into the situation calculus. We argue that the fragment of the situation calculus represented by ES is rich enough to handle the basic action theories defined by Reiter as well as Golog. Finally, we show that in the full second-order version of ES, almost all of the situation calculus can be accommodated." |
| Abstract: | "ConCon algorithm" |
| Abstract: | "The General Game Playing Project is a research project of the Stanford Logic Group, part of the Stanford University Computer Science Department. Our GGP Overview discusses the General Game Playing concept and describes our approach to research in this area. The GGP website contains information the Logic Group's research in general game playing, and forms the central resource for General Game Playing Competitions, the first of which was held at AAAI '05 in Pittsburgh. The website also hosts a GGP Game Manager, allowing General Game Players to connect and play single or multi-player games online, in order to help prepare for future competitions." |
| Abstract: | "The AgentLink III Roadmap, which provides an assessment of the current situation with respect to the status of agent technologies, and indicates key directions for future development of the field, has finally been completed. The document is a substantial report that has been compiled over an extensive period, drawing on inputs from different research communities and industries across different geographical regions. It is intended as a means to aid organisations best target investments in the technology and its deployment, and for policy makers to identify and support areas of particular importance." |
| 2004 |
| Abstract: | "We propose an alternative way to represent graphs via OBDDs based on the observation that a partition of the graph nodes allows sharing among the employed OBDDs. In the second part of the paper we present a method to compute at the same time the quotient w.r.t. the maximum bisimulation and the OBDD representation of a given graph. The proposed computation is based on an OBDD-rewriting of the notion of Ackermann encoding of hereditarily finite sets into natural numbers." |
| Abstract: | "We develop an account of the kind of deliberation that an agent that is doing planning or executing high-level programs under incomplete information must be able to perform. The deliberator's job is to produce a kind of plan that does not itself require deliberation to interpret. We characterize these as epistemically feasible programs: programs for which the executing agent, at every stage of execution, by virtue of what it knew initially and the subsequent readings of its sensors, always knows what step to take next towards the goal of completing the entire program. We formalize this notion and characterize deliberation in the situation calculus based IndiGolog agent programming language in terms of it. We also show that for certain classes of problems, which correspond to those with bounded solutions and those with solutions without sensing, the search for epistemically feasible programs can be limited to programs of a simple syntactic form. Finally, we discuss implementation issues and execution monitoring and replanning too." |
| Abstract: | "Networking and query processing must be co-designed to allow data self-organization for flexible but efficient in-network storage, access, and processing." |
| Abstract: | "We introduce a new proof procedure for abductive logic programming and present two soundness results. Our procedure extends that of Fung and Kowalski by integrating abductive reasoning with constraint solving and by relaxing the restrictions on allowed inputs for which the procedure can operate correctly. An implementation of our proof procedure is available and has been applied successfully in the context of multiagent systems." |
| Abstract: | "This paper is an analysis of two knowledge representation extensions of logic programming, namely Answer Set Programming and ID-Logic. Our aim is to compare both logics on the level of declarative reading, practical methodology and formal semantics. At the level of methodology, we put forward the thesis that in many (but not all) existing applications of ASP, an ASP program is used to encode definitions and assertions, similar as in ID-Logic. We illustrate this thesis with an example and present a formal result that supports it, namely an equivalence preserving translation from a class of ID-Logic theories into ASP. This translation can be exploited also to use the current efficient ASP solvers to reason on ID-Logic theories and it has been used to implement a model generator for ID-Logic." |
| 2003 |
| Abstract: | "Imagine a different way to program in which you specify rules and facts instead of the usual linear set of instructions. That's the idea behind rule-based programming. A rule engine automatically decides how to apply the rules to your facts and hands you the result. This approach is ideal for expressing business rules and is increasingly used in enterprise computing. Jess is a popular rule engine written in Java. It's supported by Sandia Labs and has an active online community. If you have a problem that can be solved with rules, Jess in Action will show you how. (If you are not sure, read chapter 2.) Written by the creator of Jess, this book is an accessible and practical guide to rule-based system development in Java. Jess in Action first introduces rule programming concepts and teaches you the Jess language. Armed with this knowledge, you then progress through a series of fully-developed applications chosen to expose you to practical rule-based development. The book shows you how you can add power and intelligence to your Java software." |
| Abstract: | "As we move into 2003, the information society is coming of age. With Internet penetration in Western Europe and the US expected to pass 60this year, the opportunities for technological advance are enormous. The European Commission has recognised this with its eEurope initiative in which it aims to bring every citizen, home, school, business and administration online to create a digitally literate Europe. The value lies not in the objective itself, but in its ability to facilitate the advance of Europe into new ways of living and working. Just as in the first literacy revolution, our lives will change in ways never imagined. The vision of eEurope is underpinned by a technological infrastructure that is now taken for granted. Yet it provides us with the ability to pioneer radical new ways of doing business, of undertaking science, and, of managing our everyday activities. Key to this step change is the development of appropriate mechanisms to automate and improve existing tasks, to anticipate desired actions on our behalf (as human users) and to undertake them, while at the same time enabling us to stay in the loop and retain as much control as required. For many, these mechanisms are now being realised by agent technologies, which are already providing dramatic and sustained benefits in several business and industry domains, including B2B exchanges, supply chain management, car manufacturing, and so on. While there are many real successes of agent technologies to report, there is still much to be done in research and development for the full benefits to be achieved. This is especially true in the context of environments of pervasive computing devices that are envisaged in coming years. This report describes the current state-of-the-art of agent technologies and identifies trends and challenges that will need to be addressed over the next 10 years to progress the field and realise the benefits. It offers a roadmap that is the result of discussions among participants from over 150 organisations including universities, research institutions, large multinational corporations and smaller IT start-up companies. The roadmap is a living document and will continue to be developed over time, identifying successes and challenges, and pointing to future possibilities and demands. Agent technologies are fundamental to the realisation of next generation computing. Addressing the challenges identified here to focus current and future R&D is crucial." |
| Abstract: | "We introduce a middleware infrastructure that provides software services for developing and deploying high-performance parallel programming models and distributed applications on clusters and networked heterogeneous systems. This middleware infrastructure utilizes distributed agents residing on the participating machines and communicating with one another to perform the required functions. An intensive study of the parallel programming models in Java has helped identify the common requirements for a runtime support environment, which we used to define the middleware functionality. A Java-based prototype, based on this architecture, has been developed along with a Java object-passing interface (JOPI) class library. Since this system is written completely in Java, it is portable and allows executing programs in parallel across multiple heterogeneous platforms. With the middleware infrastructure, users need not deal with the mechanisms of deploying and loading user classes on the heterogeneous system. Moreover, details of scheduling, controlling, monitoring, and executing user jobs are hidden, while the management of system resources is made transparent to the user. Such uniform services are essential for facilitating the development and deployment of scalable high-performance Java applications on clusters and heterogeneous systems. An initial deployment of a parallel Java programming model over a heterogeneous, distributed system shows good performance results. In addition, a framework for the agents' startup mechanism and organization is introduced to provide scalable deployment and communication among the agents. (30 References)." |
| Abstract: | "The provisioning of Web services over the wireless Internet introduces novel challenging issues for service design and implementation: from user/terminal mobility during service execution, to wide heterogeneity of portable access devices and unpredictable modifications in accessible resources. In this scenario, there are frequent provision-time changes in the context, defined as the logical set of accessible resources depending on client location, access terminal capabilities, and system/service management policies. The development of context-dependent services requires novel middlewares with full context visibility. We propose a middleware for context-aware resource management, called CARMEN, capable of supporting the automatic reconfiguration of wireless Internet services in response to context changes without any intervention on the service logic. CARMEN determines the context on the basis of metadata, which include declarative management policies and profiles for user preferences, terminal capabilities, and resource characteristics. In addition, CARMEN exploits the mobile agent technology to implement mobile middleware components that follow the provision-time movement of clients to support locally their customized service access. The proposed middleware shows how metadata and mobile agents can favor component reusability and automatic service reconfiguration, by reducing the development/ deployment complexity. (49 References)." |
| Abstract: | "In this paper we describe a formalism for integrating the SHOP HTN planning system with the IMPACT multi-agent environment. We define the A-SHOP algorithm, an agentized adaptation of the SHOP planning algorithm that takes advantage of IMPACT's capabilities for interacting with external agents, performing mixed symbolic/numeric computations, and making queries to distributed, heterogeneous information sources (such as arbitrary legacy and/or specialized data structures or external databases). We show that A-SHOP is both sound and complete if certain conditions are met. (42 References)." |
| Abstract: | "We study the complexity of the Subgraph Bisimulation Problem, which relates to Graph Bisimulation as Subgraph Isomorphism relates to Graph Isomorphism, and we prove its NP-Completeness. Our analysis is motivated by its applications to semistructured databases. (10 References)." |
| Abstract: | "CoABS Grid is middleware that integrates heterogeneous agent-based, object-based, and legacy systems. It includes a method-based application programming interface to register agents, advertise agent capabilities, discover agents based on their capabilities, and send messages between agents. Agent registration and discovery are reliant on one or more lookup services. The experiments discussed investigate how timing of sequential agent registration and lookup varies as the total number of registered agents increases. No degradation in performance was observed in experiments with up to 10,000 agents for lookup. Minimal degradation in registration time was observed as the number of registered agents increased. Further experiments are planned. (5 References)." |
| Abstract: | "This paper addresses the problem of ensuring that agents' plans are epistemically feasible in multiagent systems specications. We propose some solutions within the Cognitive Agents Specication Language (CASL). We define a subjective execution construct Subj that causes the plan to be executed in terms of the agent's knowledge state, rather than in terms of the world state. The denition assumes that the agent does not do planning or lookahead, and chooses arbitrarily among the actions allowed by the plan. We also define another deliberative execution operator Delib for smarter agents that do planning. We show how these notions can be used to express whether a process is epistemically feasible for its agent(s) in several types of situations. More generally, the paper shows how a formalization of epistemic feasibility can be integrated with a transition-system semantics for an agent programming/specication language." |
| Abstract: | "Sensor networks can be considered distributed computing platforms with many severe constraints, including limited CPU speed, memory size, power, and bandwidth. Individual nodes in sensor networks are typically unreliable and the network topology dynamically changes, possibly frequently. Sensor networks also differ because of their tight interaction with the physical environment via sensors and actuators. Because of this interaction, we find that sensor networks are very data-centric. Due to all of these differences, many solutions developed for general distributed computing platforms and for ad-hoc networks cannot be applied to sensor networks. After discussing several motivating applications, this paper first discusses the state of the art with respect to general research challenges, then focuses on more specific research challenges that appear in the networking, operating system, and middleware layers. For some of the research challenges, initial solutions or approaches are identified." |
| Abstract: | "Mozart/Oz" |
| Abstract: | "We present a new polynomial-space algorithm, called Adopt, for distributed constraint optimization (DCOP). DCOP is able to model a large class of collaboration problems in multi-agent systems where a solution within given quality parameters must be found. Existing methods for DCOP are not able to provide theoretical guarantees on global solution quality while operating both efficiently and asynchronously. Adopt is guaranteed to find an optimal solution, or a solution within a user-specified distance from the optimal, while allowing agents to execute asynchronously and in parallel. Adopt obtains these properties via a distributed search algorithm with several novel characteristics including the ability for each agent to make local decisions based on currently available information and without necessarily having global certainty. Theoretical analysis shows that Adopt provides provable quality guarantees, while experimental results show that Adopt is signifi- cantly more efficient than synchronous methods. The speedups are shown to be partly due to the novel search strategy employed and partly due to the asynchrony of the algorithm." |
| Abstract: | "Concerns grue paradox" |
| Abstract: | "The construction of multi-agent systems demands specification of the required agent behaviours to provide documented requirements for the design and implementation phases. From a lengthy experience in the engineering of multi-agent simulations for military operations research, a methodology for the analysis and specification of agent behaviours is proposed. The methodology builds upon the existing use case modelling techniques provided by the Unified Modeling Language (UML) and is in keeping with the agent extensions to the UML proposed elsewhere. Accompanying the elaboration of the methodology is a case-study from a specific multi-agent air combat simulation." |
| 2002 |
| Abstract: | "This volume is based on the papers that were presented at the International Conference `Model-Based Reasoning: Scientific Discovery, Technological Innovation, Values' (MBR'01), held at the Collegio Ghislieri, University of Pavia, Pavia, Italy, in May 2001. The previous volume Model-Based Reasoning in Scientific Discovery, edited by L. Magnani, N.J. Nersessian, and P. Thagard (Kluwer Academic/Plenum Publishers, New York, 1999; Chinese edition, China Science and Technology Press, Beijing, 2000), was based on the papers presented at the first `model-based reasoning' international conference, held at the same venue in December 1998. The presentations given at the Conference explore how scientific thinking uses models and exploratory reasoning to produce creative changes in theories and concepts. Some address the problem of model-based reasoning in ethics, especially pertaining to science and technology, and stress some aspects of model-based reasoning in technological innovation. The study of diagnostic, visual, spatial, analogical, and temporal reasoning has demonstrated that there are many ways of performing intelligent and creative reasoning that cannot be described with the help only of traditional notions of reasoning such as classical logic. Understanding the contribution of modeling practices to discovery and conceptual change in science requires expanding scientific reasoning to include complex forms of creative reasoning that are not always successful and can lead to incorrect solutions. The study of these heuristic ways of reasoning is situated at the crossroads of philosophy, artificial intelligence, cognitive psychology, and logic; that is, at the heart of cognitive science. There are several key ingredients common to the various forms of model-based reasoning. The term `model' comprises both internal and external representations. The models are intended as interpretations of target physical systems, processes, phenomena, or situations. The models are retrieved or constructed on the basis of potentially satisfying salient constraints of the target domain. Moreover, in the modeling process, various forms of abstraction are used. Evaluation and adaptation take place in light of structural, causal, and/or functional constraints. Model simulation can be used to produce new states and enable evaluation of behaviors and other factors. The various contributions of the book are written by interdisciplinary researchers who are active in the area of creative reasoning in science and technology, and are logically and computationally oriented: the most recent results and achievements about the topics above are illustrated in detail in the papers. Logical Aspects of Model-Based Reasoning. A Case Study of the Design and Implementation of Heterogeneous Reasoning Systems; N. Swoboda, G. Allwein. A Logical Approach to the Analysis of Metaphors; I. D'Hanis. Ampliative Adaptive Logics and the Foundation of Logic-Based Approaches to Abduction; J. Meheus, et al. Diagrammatic Inference and Graphical Proof; L.A. Pineda. A Logical Analysis of Graphical Consistency Proofs; A. Shimojima. Adaptive Logics for Non-Explanatory and Explanatory Diagnostic Reasoning; D. Provijn, E. Weber. Model-Guided Proof Planning; S. Choi, M. Kerber. Degrees of Abductive Boldness; I.C. Burger, J. Heidema. Scientific Explanation and Modified Semantic Tableaux; A. Nepomuceno-Fernádez. Computational Aspects of Model-Based Reasoning. Computational Discovery of Communicable Knowledge; P. Langley, et al. Encoding and Using Domain Knowledge on Population Dynamics for Equation Discovery; S. Dzeroski, L. Todorovski. Reasoning about Models of Nonlinear Systems; E. Stolle, et al. Model-Based Diagnosis of Dynamic Systems: Systematic Conflict Generation; B. Górny, A. Ligeza. Modeling Through Human-Computer Interactions and Mathematical Discourse; G. Menezes da Nóbrega, et al. Combining Strategy and Sub-models for the Objectified Communication of Research Programs; E. Finkeissen. Subject Index. Author Index." |
| Abstract: | "Coordination and cooperation are crucial notions in multi-agent systems. We provide a constraint programming language called GrAPL, with facilities for group communication, group formation and group collaboration. GrAPL includes three novel statements. Two of these enable groups of agents to communicate about possible constraints on a specific action they might do together. If the demands of the agents are compatible, the group reaches an agreement regarding future executions of the action discussed. The third statement is synchronised action execution. Groups of agents can perform an action together, as long as their constraints on the action are satisfied." |
| Abstract: | "In order to capture the concept of common knowledge, various extensions of multi-modal epistemic logics, such as fixed-point ones and infinitary ones, have been proposed. Although we have now a good list of such proposed extensions, the relationships among them are still unclear. The purpose of this paper is to draw a map showing the relationships among them. In the propositional case, these extensions turn out to be all Kripke complete and can be comparable in a meaningful manner. F. Wolter showed that the predicate extension of the Halpern-Moses fixed-point type common knowledge logic is Kripke incomplete. However, if we go further to an infinitary extension, Kripke completeness would be recovered. Thus there is some gap in the predicate case. In drawing the map, we focus on what is happening around the gap in the predicate case. The map enables us to better understand the common knowledge logics as a whole. (24 References)." |
| Abstract: | "This article is an edited transcript of a lecture given at IJCAI-99, Stockholm, Sweden, on 4 August 1999. The article summarizes concepts, principles, and tools that were found useful in applications involving causal modeling. The principles are based on structural-model semantics in which functional (or counterfactual) relationships representing autonomous physical processes are the fundamental building blocks. The article presents the conceptual basis of this semantics, illustrates its application in simple problems, and discusses its ramifications to computational and cognitive problems concerning causation. (27 References)." |
| Abstract: | "This paper addresses the issue of moving agent technology to the mainstream, looking from various perspectives at the mainstreaming process that can take place during a technology life cycle, radically moving its status from a supposedly good idea to an actual economic and industrial workhorse that lends itself useful in everyday life. While there is serious evidence that agent technology is approaching this critical point, it is by no means possible to tell whether agent technology will eventually be adopted on a global scale or not. However, looking at the various factors that can make the difference between acceptance and oblivion, a mainstreaming strategy can be set up. We claim that agent middleware has to play a fundamental role in this strategy, and we motivate our belief on the basis of general considerations and on our actual experience with the JADE agent platform. (30 References)." |
| Abstract: | "Abstract: Despite the significant progress in multiagent teamwork, existing research does not address the optimality of its prescriptions nor the complexity of the teamwork problem. Without a characterization of the optimality-complexity tradeoffs, it is impossible to determine whether the assumptions and approximations made by a particular theory gain enough efficiency to justify the losses in overall performance. To provide a tool for use by multiagent researchers in evaluating this tradeoff, we present a unified framework, the COMmunicative Multiagent Team Decision Problem (COM-MTDP). The COM-MTDP model combines and extends existing multiagent theories, such as decentralized partially observable Markov decision processes and economic team theory. In addition to their generality of representation, COM-MTDPs also support the analysis of both the optimality of team performance and the computational complexity of the agents' decision problem. In analyzing complexity, we present a breakdown of the computational complexity of constructing optimal teams under various classes of problem domains, along the dimensions of observability and communication cost. In analyzing optimality, we exploit the COM-MTDP's ability to encode existing teamwork theories and models to encode two instantiations of joint intentions theory taken from the literature. Furthermore, the COM-MTDP model provides a basis for the development of novel team coordination algorithms. We derive a domain-independent criterion for optimal communication and provide a comparative analysis of the two joint intentions instantiations with respect to this optimal policy. We have implemented a reusable, domain-independent software package based on COM-MTDPs to analyze teamwork coordination strategies, and we demonstrate its use by encoding and evaluating the two joint intentions strategies within an example domain." |
| Abstract: | "The subgraph isomorphism problem, that of finding a copy of one graph in another, has proved to be intractable except when certain restrictions are placed on the inputs. In this paper, we introduce a new property for graphs (a generalization on bounded degree) and extend the known classes of inputs for which polynomial-time subgraph isomorphism algorithms are attainable. In particular, if the removal of any set of at most k vertices from an n-vertex graph results in connected components, we say that the graph is a -bounded fragmentation graph. We present a polynomial-time algorithm for finding a subgraph of H isomorphic to a graph G when G is a -bounded fragmentation graph and H has bounded treewidth; these results are extended to handle graphs of locally bounded treewidth (a generalization of treewidth) when G is a -bounded fragmentation graph and has constant diameter." |
| Abstract: | "Consumers and businesses have access to vast stores of information on the Internet, ranging from newspapers, shopping catalogs, restaurant guides, classified ads, jobs listings, dating services to discussion groups and e-mail. All this information is typically accessible only while users are in front of a computer at home or in an office. Wireless devices allow unprecedented access to information from any location at any time. The presentation of this information must be tailored to the constraints of mobile devices. Small screens, slower connections, high latency and limited input capabilities present new challenges. Agents that learn user’s preferences and select information for the user are a convenience when displaying information on a 19-inch desktop monitor accessed over a broadband connection; they are essential on a handheld wireless device. This paper summarizes commercially deployed systems using machine learning methods for personalizing mobile information delivery." |
| 2001 |
| Abstract: | "In this book, we present modal logic from a modern semantically-oriented perspective -- that is, as a tool for talking about graphs. We explore the mathematical ramifications of this perspective, discussing such topics as bisimulations between models, frame definability (including the Sahlqvist and Goldblatt-Thomason Theorems), completeness and incompleteness (including rules for the undefinable and step-by-step constructions), the algebra of modal logic (including the Jónsson-Tarski Theorem and its consequences), and the decidability, undecidability, and computational complexity of modal logic. We round off the book with a discussion of six of our favorite topics in extended modal logic: logical modalities, since-until logic, hybrid logic, multi-dimensional modal logic, the guarded fragment, and a Lindström-style theorem for modal logic. We had two main reasons for writing this book. Firstly, we felt that the modern semantically-oriented perspective on modal logic, and its ramifications, were not widely enough known. Second, we felt that there was an awful lot of technical material in the modal literature that deserved a wider audience." |
| Abstract: | "Volume I: Elements of Classical Logic, deals with the background to what has come to be considered the standard formulation of predicate logic - both as far as its semantics and proof theory are concerned. The central chapter on predicate logic is followed by chapters outlining various alternative, but essentially equivalent ways of constructing the semantics for first-order logic as well as its proof theory. In addition, this volume contains a discussion of higher-order extensions of first-order logic and a compendium of the algorithmic and decision-theoretic prerequisites in the study of logical systems. Volume II: Extensions of Classical Logic, surveys the most significant intensional' extensions of predicate logic and their applications to various philosophical fields of inquiry. The twelve chapters in this volume together provide a succinct introduction to a variety of intensional frameworks, a discussion of the most well-known logical systems, as well as an overview of major applications and of the open problems in the respective fields. Volume III: Alternatives to Classical Logic, consists of a series of surveys of some of the alternatives to the basic assumptions of classical logic. These include many-valued logic, partial logic, free logic, relevance and entailment logics, dialogue logic, quantum logic, and intuitionism. Volume IV: Topics in the Philosophy of Language, presents a panorama of the applications of logical tools and methods in the formal analysis of natural language. Since a number of developments in philosophical logic were originally stimulated by concern arising in the semantic analysis of natural language discourse, the chapters in this volume provide some criteria of evaluation of the applications of work in philosophical logic. In revealing both the adequacies and inadequacies of logical investigations in the semantic structures of natural discourse, these chapters also point the way to future developments in philosophical logic in general and thus close again the circle of inquiry relating logic and language." |
| Abstract: | "Volume II: Extensions of Classical Logic, surveys the most significant intensional' extensions of predicate logic and their applications to various philosophical fields of inquiry. The twelve chapters in this volume together provide a succinct introduction to a variety of intensional frameworks, a discussion of the most well-known logical systems, as well as an overview of major applications and of the open problems in the respective fields." |
| Abstract: | "Volume II: Extensions of Classical Logic, surveys the most significant intensional' extensions of predicate logic and their applications to various philosophical fields of inquiry. The twelve chapters in this volume together provide a succinct introduction to a variety of intensional frameworks, a discussion of the most well-known logical systems, as well as an overview of major applications and of the open problems in the respective fields." |
| Abstract: | "Volume II: Extensions of Classical Logic, surveys the most significant intensional' extensions of predicate logic and their applications to various philosophical fields of inquiry. The twelve chapters in this volume together provide a succinct introduction to a variety of intensional frameworks, a discussion of the most well-known logical systems, as well as an overview of major applications and of the open problems in the respective fields." |
| Abstract: | "Volume II: Extensions of Classical Logic, surveys the most significant intensional' extensions of predicate logic and their applications to various philosophical fields of inquiry. The twelve chapters in this volume together provide a succinct introduction to a variety of intensional frameworks, a discussion of the most well-known logical systems, as well as an overview of major applications and of the open problems in the respective fields." |
| Abstract: | "Volume II: Extensions of Classical Logic, surveys the most significant intensional' extensions of predicate logic and their applications to various philosophical fields of inquiry. The twelve chapters in this volume together provide a succinct introduction to a variety of intensional frameworks, a discussion of the most well-known logical systems, as well as an overview of major applications and of the open problems in the respective fields." |
| Abstract: | "Volume II: Extensions of Classical Logic, surveys the most significant intensional' extensions of predicate logic and their applications to various philosophical fields of inquiry. The twelve chapters in this volume together provide a succinct introduction to a variety of intensional frameworks, a discussion of the most well-known logical systems, as well as an overview of major applications and of the open problems in the respective fields." |
| Abstract: | "We provide a resolution-based proof procedure for modal, description and hybrid logic that improves on previous proposals in important ways. It avoids translations into large undecidable logics, and works directly on modal, description or hybrid logic formulas instead. In addition, by using the hybrid machinery it avoids the complexities of earlier propositional resolution-based methods for modal logic. It combines ideas from the method of prefixes used in tableaux, and resolution ideas in such a way that some of the heuristics and optimizations devised in either field are applicable." |
| Abstract: | "We discuss from a practical point of view a number of issues involved in writing distributed Internet and WWW applications using LP/CLP systems. We describe PiLLoW, a public-domain Internet and WWW programming library for LP/CLP systems that we have designed to simplify the process of writing such applications. PiLLoW provides facilities for accessing documents and code on the WWW; parsing, manipulating and generating HTML and XML structured documents and data; producing HTML forms; writing form handlers and CGI-scripts; and processing HTML/XML templates. An important contribution of PiLLoW is to model HTML/XML code (and, thus, the content of WWW pages) as terms. The PiLLoW library has been developed in the context of the Ciao Prolog system, but it has been adapted to a number of popular LP/CLP systems, supporting most of its functionality. We also describe the use of concurrency and a high-level model of client-server interaction, Ciao Prolog's active modules, in the context of WWW programming. We propose a solution for client-side downloading and execution of Prolog code, using generic browsers. Finally, we also provide an overview of related work on the topic." |
| Abstract: | "Association-rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a priori algorithm is only effective when the only rules of interest are relationships that occur very frequently...." |
| Abstract: | "Autonomous agents are systems capable of autonomous decision-making in real-time environments. Computation is a valuable resource for such decision-making, and yet the amount of computation that an autonomous agent may carry out will be limited. It follows that an agent must be equipped with a mechanism that enables it to make the best possible use of the computational resources at its disposal. In this paper we review three approaches to the control of computation in resource-bounded agents. In addition to a detailed description of each framework, this paper compares and contrasts the approaches, and lists the advantages and disadvantages of each. (38 References)." |
| Abstract: | "Given domain-specific background knowledge and data in the form of examples, an Inductive Logic Programming (ILP) system extracts models in the data-analytic sense. We view the model-selection step facing an ILP system as a decision problem, the solution of which requires knowledge of the context in which the model is to be deployed. In this paper, {"}context{"} will be defined by the current specification of the prior class distribution and the client's preferences concerning errors of classification. Within this restricted setting, we consider the use of an ILP system in situations where: (a) contexts can change regularly. This can arise for example, from changes to class distributions or misclassification costs; and (b) the data are from observational studies. That is, they may not have been collected with any particular context in mind. Some repercussions of these are: (a) any one model may not be the optimal choice for all contexts; and (b) not all the background information provided may be relevant for all contexts. Using results from the analysis of Receiver Operating Characteristic curves, we investigate a technique that can equip an ILP system to reject those models that cannot possibly be optimal in any context. We present empirical results from using the technique to analyse two datasets concerned with the toxicity of chemicals (in particular, their mutagenic and carcinogenic properties). Clients can, and typically do, approach such datasets with quite different requirements. For example, a synthetic chemist would require models with a low rate of commission errors which could be used to direct efficiently the synthesis of new compounds. A toxicologist on the other hand, would prefer models with a low rate of omission errors. This would enable a more complete identification of toxic chemicals at a calculated cost of misidentification of non-toxic cases as toxic. The approach adopted here attempts to obtain a solution that contains models that are optimal for each such user according to the cost function that he or she wishes to apply. In doing so, it also provides one solution to the problem of how the relevance of background predicates is to be assessed in ILP." |
| Abstract: | "As a part of my group's activities on the extension of the fluent calculus (Holldobler and Schneeberger 1990; Thielscher 1998), I've been working to provide an efficient inference engine for the fluent calculus by using the efficiency of binary decision diagrams (BDDs) (Bryant 1986). In the past, BDDs have significantly improved the performance of algorithms and enabled the solution of new classes of problems in areas such as formal verification and logic synthesis (see, for example, Burch et al. [1992]). Surprisingly, BDDs have only recently been introduced to implement the solution of planning problems (Cimatti et al. 1997). The goal of our project was to investigate whether BDDs might also help to increase the efficiency of algorithms solving problems in the field of reasoning about action and change. For a start, I have implemented the solution of fluent calculus planning problems restricted to deterministic actions and propositional fluents (Holldobler and Storr 2000; Storr 2001)." |
| Abstract: | "The author discusses games of both perfect and imperfect information at two levels of structural detail: players' local actions, and their global powers for determining outcomes of the game. Matching logical languages are proposed for both. In particular, at the {"}action level{"}, imperfect information games naturally model a combined {"}dynamic-epistemic language{"}--and correspondences are found between special axioms in this language and particular modes of playing games with their information dynamics. At the {"}outcome level{"}, the paper presents suitable notions of game equivalence, and some simple representation results. Copyright 2001 by Blackwell Publishing Ltd and the Board of Trustees of the Bulletin of Economic Research" |
| Abstract: | "The formal possible-worlds analysis of counterfactuals has tended to concentrate on their semantics and logic, with their pragmatics being given informally. However, if counterfactuals are to be of use in Artificial Intelligence, it is necessary to provide formal pragmatics for them. This is done in this paper by combining work on the representation of common sense reasoning about events with an appropriate semantics for counterfactuals. The resulting combination provides a unified framework for formal reasoning about actual and counterfactual events." |
| 2000 |
| Abstract: | "Among the many approaches to formal reasoning about programs, Dynamic Logic enjoys the singular advantage of being strongly related to classical logic. Its variants constitute natural generalizations and extensions of classical formalisms. For example, Propositional Dynamic Logic (PDL) can be described as a blend of three complementary classical ingredients: propositional calculus, modal logic, and the algebra of regular events. In First-Order Dynamic Logic (DL), the propositional calculus is replaced by classical first-order predicate calculus. Dynamic Logic is a system of remarkable unity that is theoretically rich as well as of practical value. It can be used for formalizing correctness specifications and proving rigorously that those specifications are met by a particular program. Other uses include determining the equivalence of programs, comparing the expressive power of various programming constructs, and synthesizing programs from specifications. This book provides the first comprehensive introduction to Dynamic Logic. It is divided into three parts. The first part reviews the appropriate fundamental concepts of logic and computability theory and can stand alone as an introduction to these topics. The second part discusses PDL and its variants, and the third part discusses DL and its variants. Examples are provided throughout, and exercises and a short historical section are included at the end of each chapter." |
| Abstract: | "Factored MDPs" |
| Abstract: | "For pt.II see ibid., no.108, p.257-307 (1999). In pt.I (ibid., no.108, p.179-255, 1999), there are introduced techniques to build agents on top of arbitrary data structures, and to {"}agentize{"} new/existing programs. Provided are a series of successively more sophisticated semantics for such agent systems; as these semantics become epistemically more desirable, a computational price may need to be paid. In this paper, we identify the class of weakly regular agents, by first identifying a fragment of weakly regular agent programs (WRAP). It is shown that WRAPs are definable via three parameters; safety, conflict-freedom and deontic stratifiability. Algorithms for each of these are developed. A weakly regular agent is then defined in terms of these concepts, and a regular agent is one that satisfies an additional boundedness property. We then describe a polynomial algorithm that computes (under suitable assumptions) the reasonable status set semantics of regular agents-this semantics is epistemically the most desirable. Though this semantics is coNP-complete for arbitrary agent programs, it is polynomially computable via our algorithm for regular agents. Finally, we describe our implementation architecture and provide details of how we have implemented RAPs, together with experimental results. (39 References)." |
| Abstract: | "We compare tractable classes of constraint satisfaction problems (CSPs). We first give a uniform presentation of the major structural CSP decomposition methods. We then introduce a new class of tractable CSPs based on the concept of hypertree decomposition developed in database theory, and analyze the cost of solving CSPs having bounded hypertree-width. We provide a framework for comparing parametric decomposition-based methods according to tractability criteria and compare the most relevant methods. We show that the method of hypertree decomposition dominates the others in the case of general CSPs (i.e., CSPs of unbounded arity). We also make comparisons for the restricted case of binary CSPs. Finally, we consider the application of decomposition methods to the dual graph of a hypergraph. In fact, this technique is often used to exploit binary decomposition methods for nonbinary CSPs. However, even in this case, the hypertree decomposition method turns out to be the most general method." |
| Abstract: | "Causal models defined in terms of a collection of equations, as defined by J. Pearl (1995, 1999), are axiomatized. Axiomatizations are provided for three successively more general classes of causal models: (1) the class of recursive theories (those without feedback), (2) the class of theories where the solutions to the equations are unique, and (3) arbitrary theories (where the equations may not have solutions and, if they do, they are not necessarily unique). It is shown that to reason about causality in the most general third class, we must extend the language used by D. Galles and J. Pearl (1997, 1998). In addition, the complexity of the decision procedures is characterized for all the languages and classes of models considered. (14 References)." |
| Abstract: | "This article presents Gaia: a methodology for agent-oriented analysis and design. The Gaia methodology is both general, in that it is applicable to a wide range of multi-agent systems, and comprehensive, in that it deals with both the macro-level (societal) and the micro-level (agent) aspects of systems. Gaia is founded on the view of a multi-agent system as a computational organisation consisting of various interacting roles. We illustrate Gaia through a case study tan agent-based business process management system)." |
| 1999 |
| Abstract: | "Formal learning theory is one of several mathematical approaches to the study of intelligent adaptation to the environment. The analysis developed in this book is based on a number theoretical approach to learning and uses the tools of recursive-function theory to understand how learners come to an accurate view of reality. This revised and expanded edition of a successful text provides a comprehensive, self-contained introduction to the concepts and techniques of the theory. Exercises throughout the text provide experience in the use of computational arguments to prove facts about learning." |
| Abstract: | "This is the first comprehensive introduction to multiagent systems and contemporary distributed artificial intelligence. The book provides detailed coverage of basic topics as well as several closely related ones and is suitable as a textbook. The book can be used for teaching as well as self-study, and it is designed to meet the needs of both researchers and practitioners. In view of the interdisciplinary nature of the field, it will be a useful reference not only for computer scientists and engineers, but for social scientists and management and organization scientists as well. edited by Gerhard Weiss. Includes bibliographical references and index. 1. Intelligent Agents / Michael Wooldridge -- 2. Multiagent Systems and Societies of Agents / Michael N. Huhns and Larry M. Stephens -- 3. Distributed Problem Solving and Planning / Edmund H. Durfee -- 4. Search Algorithms for Agents / Makoto Yokoo and Toru Ishida -- 5. Distributed Rational Decision Making / Tuomas W. Sandholm -- 6. Learning in Multiagent Systems / Sandip Sen and Gerhard Weiss -- 7. Computational Organization Theory / Kathleen M. Carley and Les Gasser -- 8. Formal Methods in DAI: Logic-Based Representation and Reasoning / Munindar P. Singh, Anand S. Rao and Michael P. Georgeff -- 9. Industrial and Practical Applications of DAI / H. Van Dyke Parunak -- 10. Groupware and Computer Supported Cooperative Work / Clarence Ellis and Jacques Wainer -- 11. Distributed Models for Decision Support / Jose Cuena and Sascha Ossowski -- 12. Concurrent Programming for DAI / Gul A. Agha and Nadeem Jamali -- 13. Distributed Control Algorithms for AI / Gerard Tel." |
| Abstract: | "This survey provides a conceptual introduction to agent-oriented software engineering and their role in information systems and AI. The authors also discuss how agent-oriented software engineering clarify the domain's structure of knowledge and enable knowledge sharing. (18 References)." |
| Abstract: | "For pt.I see ibid., p.179-255. In that part, we developed a language called Agent Programs for defining the operational behavior of software agents and defined a set of successively more satisfying (epistemically) semantics for such agent programs. In this part, we study the computation price to be paid (in terms of complexity) for these epistemic desiderata. In particular, we develop algorithms for the above semantics, and describe results on their computational complexity. We show that (surprisingly) the reasonable status set semantics is the easiest to compute of the semantics proposed. (27 References)." |
| Abstract: | "Over the years, many different agent programming languages have been proposed. In this paper, we propose a concept called agent programs using which the way an agent should act in various situations can be declaratively specified by the creator of that agent. Agent programs may be built on top of arbitrary pieces of software code and may be used to specify what an agent is obliged to do, what an agent may do, and what an agent may not do. In this paper, we define several successively more sophisticated and epistemically satisfying declarative semantics for agent programs. We further show that agent programs cleanly extend well understood semantics for logic programs, and thus are clearly linked to existing results on logic programming and nonmonotonic reasoning. (108 References)." |
| Abstract: | "We examine carefully the rationale underlying the approaches to belief change taken in the literature, and highlight what we view as methodological problems. We argue that to study belief change carefully, we must be quite explicit about the {"}ontology{"} or scenario underlying the belief change process. This is something that has been missing in previous work, with its focus on postulates. Our analysis shows that we must pay particular attention to two issues that have often been taken for granted: the first is how we model the agent's epistemic state. (Do we use a set of beliefs, or a richer structure, such as an ordering on worlds? And if we use a set of beliefs, in what language are these beliefs are expressed?) We show that even postulates that have been called {"}beyond controversy{"} are unreasonable when the agent's beliefs include beliefs about her own epistemic state as well as the external world. The second is the status of observations. (Are observations known to be true, or just believed? In the latter case, how firm is the belief?) Issues regarding the status of observations arise particularly when we consider iterated belief revision, and we must confront the possibility of revising by phi and then by - phi. (15 References)." |
| Abstract: | "An intriguing and relatively new metaphor in the programming community is that of an intelligent agent. The idea is to view programs as intelligent agents acting on our behalf. By using the metaphor of intelligent agents the programmer views programs as entities which have a mental state consisting of beliefs and goals. The computational behaviour of an agent is explained in terms of the decisions the agent makes on the basis of its mental state. It is assumed that this way of looking at programs may enhance the design and development of complex computational systems. To support this new style of programming, we propose the agent programming language 3APL. 3APL has a clear and formally defined semantics. The operational semantics of the language is defined by means of transition systems. 3APL is a combination of imperative and logic programming. From imperative programming the language inherits the full range of regular programming constructs, including recursive procedures, and a notion of state-based computation. States of agents, however, are belief or knowledge bases, which are different from the usual variable assignments of imperative programming. From logic programming, the language inherits the proof as computation model as a basic means of computation for querying the belief base of an agent. These features are well-understood and provide a solid basis for a structured agent programming language. Moreover, on top of that 3APL agents use so-called practical reasoning rules which extend the familiar recursive rules of imperative programming in several ways. (27 References)." |
| Abstract: | "In this paper we consider the task of matching patterns, as occur in hand-drawn symbols and schematic diagrams, by their parts and relationships. Of particular interest for computer vision is the integration of two approaches to the recognition by parts problem-graph matching and syntactic rule-based approaches. A new procedure is developed, named CLARET, which matches parts and relationships by tightly coupling the processes of matching and rule generation at run time. We have developed an interactive system for interpreting hand-drawn symbols and schematic drawings. The system operates invariant to rotation, scale, and position and projects images onto a drawing canvas. The procedure is analyzed for its ability to accommodate new symbols and answer orientation queries, and it is compared empirically with machine learning techniques. (C) 1999 Academic Press." |
| Abstract: | "Human intelligence is shaped by what is most important to us-the things that cause ecstasy, despair, pleasure, pain, and other intense emotions. The ability to separate the important from the unimportant underlies such faculties as attention, focusing, situation and outcome assessment, priority setting, judgment, taste, goal selection, credit assignment, the selection of relevant memories and precedents, and learning from experience. Al has for the most part focused on logic and reasoning in artificial situations where only relevant variables and operators are specified and has paid insufficient attention to processes of reducing the richness and disorganization of the real world to a form where logical reasoning can be applied. This article discusses the role of importance judgment in intelligence; provides some examples of research that make use of importance judgments; and offers suggestions for new mechanisms, architectures, applications, and research directions for AI." |
| Abstract: | "Within the ATAL community, the belief-desire-intention (BDI) model has come to be possibly the best known and best studied model of practical reasoning agents. However, it could be argued that the BDI model is now becoming somewhat dated: the principles of the architecture were established in the mid-1980s, and have remained essentially unchanged since then. With the explosion of interest in intelligent agents and multi-agent systems that has occurred since then, a great many other architectures have been developed, which, it could be argued, address some issues that the BDI model fundamentally fails to. The purpose of this paper is therefore to establish how the BDI model stands in relation to other contemporary models of agency, and where it should go next. (18 References)." |
| Abstract: | "Complete axiomatizations and exponential-time decision procedures are provided for reasoning about knowledge and common knowledge when there are infinitely many agents. The results show that reasoning about knowledge and common knowledge with infinitely many agents is no harder than when there are finitely many agents, provided that we can check the cardinality of certain set differences G G' where G and G' are sets of agents. Since our complexity results are independent of the cardinality of the sets G involved, they represent improvements over the previous results even with the sets of agents involved are finite. Moreover, our results make clear the extent to which issues of complexity and completeness depend on how the sets of agents involved are represented. (8 References)." |
| 1998 |
| Abstract: | "A central issue in the design of cooperative multiagent systems is how to coordinate the behavior of the agents to meet the goals of the designer. Traditionally, this has been accomplished by hand-coding the coordination strategies. However, this task is complex due to the interactions that can take place among agents. Recent work in the area has focused on how strategies can be learned. Yet, many of these systems suffer from convergence, complexity and performance problems. The paper presents a new approach for learning multiagent coordination strategies that addresses these issues. The effectiveness of the technique is demonstrated using a synthetic domain and the predator and prey pursuit problem." |
| Abstract: | "We describe a platform called IMPACT to support multiagent interactions. The platform provides a set of servers (yellow pages, thesaurus, registration, type, and interface) that facilitate agent interoperability in an application independent manner. In IMPACT agents have an associated set of service descriptions, specifying the services they provide. We develop an HTML-like language for such service descriptions. When an agent wishes to identify another agent that provides a service, the requested service must be matched, using a metric approach, against existing service descriptions. We provide a formal framework within which this may be done, and develop algorithms to compute the k nearest matches, as well as all matches within a given distance from the requested service. We report on experiments evaluating our algorithms with large data sets. (2 References)." |
| 1997 |
| Abstract: | "Many aspects of the internal and external workings of computers can be viewed, at different levels, as a series of communication processes. Communication complexity is the mathematical theory of such communication processes. It extends Shannon's information theory, allowing two-way communication and arbitrary processes. This book surveys the mathematical theory, concentrating on the question of how much communication is necessary for any particular process. This is an essential resource for graduate students and researchers in theoretical computer science, circuits, networks, VLSI, and information theory." |
| Abstract: | "This textbook provides a first introduction to mathematical logic which is closely attuned to the applications of logic in computer science. In it the authors emphasize the notion that deduction is a form of computation. While all the traditional subjects of logic are covered thoroughly - syntax, semantics, completeness, and compactness - much of the book deals with less traditional topics such as resolution theorem proving, logic programming, and non-classical logics - modal and intuitionistic - which are becoming increasingly important in computer science. The book also provides a systematic treatment of the elements of set theory, a historical overview of its subjects, and an extensive annotated bibliography. No previous exposure to logic is assumed, and so this will be suitable for upper level undergraduate or beginning graduate students in computer science or mathematics." |
| Abstract: | "Reasoning about activities in a distributed computer system at the level of the knowledge of individuals and groups allows one to abstract away from many concrete details of the system being considered. The authors make use of two notions introduced in their recent book to facilitate designing and reasoning about systems in terms of knowledge. The first notion is that of a knowledge-based program. A knowledge-based program is a syntactic object: a program with tests for knowledge. The second notion is that of a context, which captures the setting in which a program is to be executed. In a given context, a standard program (one without tests for knowledge) is represented by (i.e. corresponds in a precise sense to) a unique system. A knowledge-based program, on the other hand, may be represented by no system, one system, or many systems. They provide a sufficient condition for a knowledge-based program to be represented in a unique way in a given context. This condition applies to many cases of interest, and covers many of the knowledge-based programs considered in the literature. They also completely characterize the complexity of determining whether a given knowledge-based program has a unique representation, or any representation at all, in a given finite-state context. (35 References)." |
| Abstract: | "The RoboCup (Robot World-Cup Soccer) is an attempt to foster AI and intelligent robotics research by providing a standard problem where a wide range of technologies can be integrated and examined. The first RoboCup competition will be held at the Fifteenth International Joint Conference on Artificial Intelligence in Nagoya, Japan. A robot team must actually perform a soccer game, incorporating various technologies, including design principles of autonomous agents, multiagent collaboration, strategy acquisition, real-time reasoning, robotics, and sensor fusion. RoboCup is a task for a team of multiple fast-moving robots under a dynamic environment. Although RoboCup's final target is a world cup with real robots, RoboCup offers a software platform for research on the software aspects of RoboCup. This article describes technical challenges involved in RoboCup, rules, and the simulation environment. (35 References)." |
| Abstract: | "This paper reviews our recent work on applying inductive logic programming to the construction of natural language processing systems. We have developed a system, CHILL, that learns a parser from a training corpus of parsed sentences by inducing heuristics that control an initial overly-general shift-reduce parser. CHILL learns syntactic parsers as well as ones that translate English database queries directly into executable logical form. The ATIS corpus of airline information queries was used to test the acquisition of syntactic parsers, and CHILL performed competitively with recent statistical methods. English queries to a small database on U.S. geography were used to test the acquisition of a complete natural language interface, and the parser that CHILL acquired was more accurate than an existing hand-coded system. The paper also includes a discussion of several issues this work has raised regarding the capabilities and testing of ILP systems as well as a summary of our current research directions." |
| Abstract: | "Inspired by game theory representations, Bayesian networks, influence diagrams, structured Markov decision process models, logic programming, and work in dynamical systems, the independent choice logic (ICL) is a semantic framework that allows for independent choices (made by various agents, including nature) and a logic program that gives the consequence of choices. This representation can be used as a specification for agents that act in a world, make observations of that world and have memory, as well as a modelling tool for dynamic environments with uncertainty. The rules specify the consequences of an action, what can be sensed and the utility of outcomes. This paper presents a possible-worlds semantics for ICL, and shows how to embed influence diagrams, structured Markov decision processes, and both the strategic (normal) form and extensive (game-tree) form of games within the ICL. It is argued that the ICL provides a natural and concise representation for multi-agent decision-making under uncertainty that allows for the representation of structured probability tables, the dynamic construction of networks (through the use of logical variables) and a way to handle uncertainty and decisions in a logical representation. (57 References)." |
| Abstract: | "The long-term goal of our field is the creation and understanding of intelligence. Productive research in AI, both practical and theoretical, benefits from a notion of intelligence that is precise enough to allow the cumulative development of robust systems and general results. The concept of rational agency has long been considered a leading candidate to fulfil this role. This paper outlines a gradual evolution in the formal conception of rationality that brings it closer to our informal conception of intelligence and simultaneously reduces the gap between theory and practice. Some directions for future research are indicated. (52 References)." |
| 1996 |
| Abstract: | "The Essence of Logic is an exciting new publication that provides a concise introduction to formal logic. Making little demands on previous mathematical knowledge, this comprehensive text prepares the reader for the analysis and application of logic techniques in computing. It can also be used for the study of mathematical logic in its own right. Extensive in its coverage, each new concept is gently introduced, and then reinforced by numerous exercises and examples. This practical approach quickly develops skills needed to apply logic in a wide range of computer science disciplines." |
| Abstract: | "We introduce Mercury, a new purely declarative logic programming language designed to provide the support that groups of application programmers need when building large programs. Mercury's strong type, mode, and determinism systems improve program reliability by catching many errors at compile time. We present a new and relatively simple execution model that takes advantage of the information these systems provide, yielding very efficient code. The Mercury compiler uses this execution model to generate portable C code. Our benchmarking shows that the code generated by our implementation is significantly faster than the code generated by mature optimizing implementations of other logic programming languages." |
| Abstract: | "This paper investigates Constraint Satisfaction Problems (CSPs) that axe distributed by nature, i.e., there is a division of the CSP into sub components (agents) that axe connected via constraints, where each subcomponent includes several of the CSP variables with the constraints between them. We call such a problem a Distributed CSP (DCSP). In this paper we give a formal definition of DCSPs and present four algorithms for solving them. Two of the algorithms are based on the difference between the difficulty of solving the internal constraints in the CSP components (we call them the peripheral components) of the DCSP and the difficulty of solving the constraints between the different CSPs (the central component). The two other algorithms use local and global views of the DCSP respectively. All the algorithms permit the use of different techniques (CSP, knowledge based, and operation research algorithms) in solving each of the problem components. We probe that as long as all the selected techniques axe sound and complete, our algorithms are sound and complete. The algorithms were tested in a real distributed environment; the results show that when there is a difference between the difficulty of solving the peripheral components and the central one, taking advazltage of it may reduce significantly the amount of work (constraint checks and message passing) needed for solving the DCSP." |
| 1995 |
| Abstract: | "Epistemic logic has grown from its philosophical beginnings to find diverse applications in computer science as a means of reasoning about the knowledge and belief of agents. This book, based on courses taught at universities and summer schools, provides a broad introduction to the subject; many exercises are included together with their solutions. The authors begin by presenting the necessary apparatus from mathematics and logic, including Kripke semantics and the well-known modal logics K, T, S4 and S5. Then they turn to applications in the contexts of distributed systems and artificial intelligence: topics that are addressed include the notions of common knowledge, distributed knowledge, explicit and implicit belief, the interplays between knowledge and time, and knowledge and action, as well as a graded (or numerical) variant of the epistemic operators. The problem of logical omniscience is also discussed extensively. Halpern and Moses' theory of honest formulae is covered, and a digression is made into the realm of non-monotonic reasoning and preferential entailment. Moore's autoepistemic logic is discussed, together with Levesque's related logic of 'all I know'. Furthermore, it is shown how one can base default and counterfactual reasoning on epistemic logic." |
| Abstract: | "Computers and Thought showcases the work of the scientists who not only defined the field of artificial intelligence, but who are responsible for having developed it into what it is today. Originally published in 1963, this collection includes twenty classic papers by such pioneers as A. M. Turing and Marvin Minsky who were behind the pivotal advances in artificially simulating human thought processes with computers. Among the now hard-to-find articles are reports of computer programs that play chess and checkers, prove theorems in logic and geometry, solve problems in calculus, balance assembly lines, recognize visual temporal patterns, and communicate in natural language. The reports of simulation of cognitive processes include computer models of human behavior in logic problems, deciding on common stock portfolios, and carrying out social interaction. Models of verbal learning behavior, predictive behavior in two-choice experiments, and concept formation are also included." |
| Abstract: | "The problem of logical omniscience reappears in the popular Kripke semantics for logics of knowledge. Under such semantics, a knower i has an accessibility relation approximately=/sub i/ which is usually an equivalence relation, but need not be assumed to be such for this discussion. Intuitively, s approximately=/sub i/ t means that the worlds s and t result in the same state of information for i. Then the formula K/sub i/( phi ) holds at a possible world (or state) s iff phi holds at all t accessible from s, i.e. at all t such that s approximately=/sub i/ t. It follows immediately that if phi is logically true then K/sub i/( phi ) holds at s, since it must hold at all such t. Also if K/sub i/( phi ) and K/sub i/( phi to psi ) hold at s then so does K/sub i/( psi ). Thus what i knows at s includes all logical truths and is closed under logical consequence. Given this state of affairs, i of course has no need of reasoning since i already knows everything that i might derive through it. But since real people (or processors) do not have these advantages, a more realistic theory of knowledge must allow for a knower not to know some logical truths or not to know some consequences of things that she knows. Recent literature has had a fair number of papers addressed to this issue but the problem is still largely open. Our purpose here is to survey some of the previous work and offer one or two suggestions. (15 References)." |
| 1994 |
| Abstract: | "In pattern recognition, the graph matching problem involves the matching of a sample data graph with the subgraph of a larger model graph where vertices and edges correspond to pattern parts and their relations. In this paper, we present rulegraphs, a new method that combines the graph matching approach with rule-based approaches from machine learning. This new method reduces the cardinality of the (NP-complete) graph matching problem by replacing model part, and their relational attribute states, by rules which depict attribute bounds and evidence for different classes. We show how rulegraphs, when combined with techniques for checking feature label-compatibilities, not only reduce the search space but also improve the uniqueness of the matching process. (37 References)." |
| Abstract: | "We present and compare two new techniques for learning relational structures (RSs) as they occur in 2D pattern and 3D object recognition. These techniques, namely, evidence-based networks (EBS-NNets) and Rulegraphs combine techniques from computer vision with those from machine learning and graph matching. The EBS-NNet has the ability to generalize pattern rules from training instances in terms of bounds on both unary (single part) and binary (part relation) numerical features. It also learns the compatibilities between unary and binary feature states in defining different pattern classes. Rulegraphs check this compatibility between unary and binary rules by combining evidence theory with graph theory. The two systems are tested and compared using a number of different pattern and object recognition problems. (21 References)." |
| Abstract: | "We describe a representation of inheritance networks with strict and defeasible links as first-order theories in which different priority policies can be expressed within the theory. We present a {"}preferred model{"} semantics for such theories by adapting the perfect model semantics for logic programs, and briefly discuss relationships between this semantics and other proposed semantics for inheritance networks. (26 References)." |
| Abstract: | "The standard model of knowledge in multi-agent systems suffers from what has been called the logical omniscience problem: agents know all tautologies, and know all the logical consequences of their knowledge. For many types of analysis, this does not turn out to be a problem. Knowledge is viewed as being ascribed by the system designer to the agents; agents are not assumed to compute their knowledge in any way, nor is it assumed that they can necessarily answer questions based on their knowledge. Nevertheless, in many applications that we are interested in, agents need to act on their knowledge. In such applications, an externally ascribed notion of knowledge is insufficient: clearly an agent can base his actions only on what he explicitly knows. Furthermore, an agent that has to act on his knowledge has to be able to compute this knowledge; we do need to take into account the algorithms available to the agent, as well as the {"}effort{"} required to compute knowledge. We show how the standard model can be modified in a natural way to take the computational aspects of knowledge into account. (30 References)." |
| 1993 |
| Abstract: | "Distributed artificial intelligence systems, in which multiple agents interact to improve their individual performance and to enhance the systems' overall utility, are becoming an increasingly pervasive means of conceptualising a diverse range of applications. As the discipline matures, researchers are beginning to strive for the underlying theories and principles which guide the central processes of coordination and cooperation. Here agent communities are modelled using a distributed goal search formalism, and it is argued that commitments (pledges to undertake a specific course of action) and conventions (means of monitoring commitments in changing circumstances) are the foundation of coordination in multi-agent systems. An analysis of existing coordination models which use concepts akin to commitments and conventions is undertaken before a new unifying framework is presented. Finally, a number of prominent coordination techniques which do not explicitly involve commitments or conventions are reformulated in these terms to demonstrate their compliance with the central hypothesis of this paper. (95 References)." |
| Abstract: | "rete leaps" |
| 1992 |
| Abstract: | "We review and re-examine possible-worlds semantics for propositional logics of knowledge and belief with three particular points of emphasis: (1) we show how general techniques for finding decision procedures and complete axiomatizations apply to models for knowledge and belief, (2) we show how sensitive the difficulty of the decision procedure is to such issues as the choice of modal operators and the axiom system, and (3) we discuss how notions of common knowledge and distributed knowledge among a group of agents fit into the possible-worlds framework, As far as complexity is concerned, we show, among other results, that while the problem of deciding satisfiability of an S5 formula with one agent is NP-complete, the problem for many agents is PSPACE-complete. Adding a distributed knowledge operator does not change the complexity, but once a common knowledge operator is added to the language, the problem becomes complete for exponential time." |
| 1991 |
| 1990 |
| Abstract: | "Notes: Spine title: Automated deduction in nonclassical logics. Bibliography: [228]-234. Subjects: Proof theory. Modality (Logic) Intuitionistic mathematics. ISBN: 0262231441 Library Congress Number: 89014539" |
| 1989 |
| Abstract: | "This book develops and demonstrates efficient matrix proof methods for automated deduction within an important and comprehensive class of first order and intuitionistic logics. Traditional techniques for the design of efficient proof systems are abstracted from their original setting which allows their application to a wider class of mathematical logic. The logics discussed are used throughout computer science and artificial intelligence. Contents: Introduction I. Automated Deduction in Classical Logic. Proof search in classical sequent calculi. A matrix characterization of classical validity. II. Automated Proof Deduction in Modal Logics. The semantics and proof theory of modal logics. Proof search in modal sequent calculi. Matrix characterizations of modal validity. Alternative proof methods for modal logics. Matrix based proof search. III. Automated Deduction in Intuitionistic Logic. A Matrix proof method. Conclusions. Lincoln A. Wallen is a B.P. Venture Research Fellow at the University of Texas at Austin Automated Deduction in Nonclassical Logics is included in the Artificial Intelligence series, edited by Patrick Winston Michael Brady, and Daniel Bobrow." |
| 1988 |
| 1987 |
| Abstract: | "The author presents a series of operators of apparently increasing power which when added to first-order logic produce a series of languages in which exactly the properties checkable in a certain complexity class may be expressed. He gives alternate characterizations of the most important complexity classes. He also introduces reductions appropriate for the setting: first-order translations, and a restricted, quantifier free version of these called projection translations. He shows that projection translations are a uniform version of Valiant's projections, and that the usual complete problems remain complete via these very restrictive reductions. (30 References)." |
| Abstract: | "A fundamental computational limit on automated reasoning and its effect on knowledge representation is examined. Basically, the problem is that it can be more difficult to reason correctly with one representational language than with another and, moreover, that this difficulty increases dramatically as the expressive power of the language increases. This leads to a tradeoff between the expressiveness of a representational language and its computational tractability. It is shown that this tradeoff can be seen to underlie the differences among a number of existing representational formalisms, in addition to motivating many of the current research issues in knowledge representation. (37 References)." |
| 1986 |
| 1985 |
| 1984 |
| Abstract: | "The transaction commit problem in a distributed database system is an instance of the Weak Byzantine Generals problem. It is shown that even under the assumption that a process can fail only by “crashing”—failing to send any more messages—a solution to this problem that can tolerate k failures must, in the worst case, require at least k + 1 message-passing delays. Under this same assumption, a simple solution that exhibits the optimal worst-case behavior is given." |
| 1983 |
| 1982 |
| Abstract: | "Rete" |
| 1981 |
| 1980 |
| Abstract: | "Humans and intelligent computer programs must often jump to the conclusion that the objects they can determine to have certain properties or relations are the only objects that do. Circumscription formalizes such conjectural reasoning. (12 References)." |
| 1979 |
| 1976 |
| 1975 |
| 1973 |
| 1971 |
| 1970 |
| 1968 |
| Abstract: | "The Missionaries and Cannibals problem" |
| 1962 |
| no year |
| Abstract: | "This book is about recent changes in the design of intelligent machines. New computer models of vision and navigation in animals suggest a different way to build machines. Cognition is viewed not just in terms of high-level {"}expertise |
| Abstract: | "Buddy descriptors: Electrical Engineering. Service provider is ENGnetBASE. Subtitle: Compact Wireless and Wired Sensing Systems.As the field of communications networks continues to evolve, a very interesting and challenging area *wireless sensor networks * is rapidly coming of age. A wireless sensor network consists of a large number of sensor nodes that may be randomly and densely deployed." |
Disclaimer: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All person copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Bibliography last modified: Fri Aug 6 11:18:01 2010 translated from BibTEX by bibtex2html