Most autonomous robots are equipped with restricted, unreliable, and inaccurate sensors and effectors and operate in complex and dynamic environments. A successful approach to deal with the resulting uncertainty is the use of controllers that prescribe the robots' behavior in terms of concurrent reactive plans (CRPs) -- plans that specify how the robots are to react to sensory input in order to accomplish their jobs reliably (e.g., McDermott, 1992a; Beetz, 1999). Reactive plans are successfully used to produce situation specific behavior, to detect problems and recover from them automatically, and to recognize and exploit opportunities (Beetz et al., 2001). These kinds of behaviors are particularly important for autonomous robots that have only uncertain information about the world, act in dynamically changing environments, and are to accomplish complex tasks efficiently. Besides reliability and flexibility, foresight is another important capability of competent autonomous robots (McDermott, 1992a).

We present a uniform non-monotonic solution to the problems of reasoning about action on the basis of an argumentation-theoretic approach. Our theory is provably correct relative to a sensible minimisation policy introduced on top of a temporal propositional logic. Sophisticated problem domains can be formalised in our framework. As much attention of researchers in the field has been paid to the traditional and basic problems in reasoning about actions such as the frame, the qualification and the ramification problems, approaches to these problems within our formalisation lie at heart of the expositions presented in this paper.

A general game playing system is one that can accept a formal description of a game and play the game effectively without human intervention. Unlike specialized game players, such as Deep Blue, general game players do not rely on algorithms designed in advance for specific games; and, unlike Deep Blue, they are able to play different kinds of games. In order to promote work in this area, the AAAI is sponsoring an open competition at this summer's Twentieth National Conference on Artificial Intelligence. This article is an overview of the technical issues and logistics associated with this summer's competition, as well as the relevance of general game playing to the long range-goals of artificial intelligence.

Many description logics (DLs) combine knowledge representation on an abstract, logical level with an interface to 'concrete' domains like numbers and strings with built-in predicates such as >, +, and prefix-of. These hybrid DLs have turned out to be useful in several application areas, such as reasoning about conceptual database models. We propose to further extend such DLs with key constraints that allow the expression of statements like 'US citizens are uniquely identified by their social security number'. Based on this idea, we introduce a number of natural description logics and perform a detailed analysis of their decidability and computational complexity. It turns out that naive extensions with key constraints easily lead to undecidability, whereas more careful extensions yield NExpTime-complete DLs for a variety of useful concrete domains.

This is the third of three papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal has been to define a representation in which this structure is apparent and can be exploited to improve computational performance. The first paper surveyed existing work that (knowingly or not) exploited problem structure to improve the performance of satisfiability engines, and the second paper showed that this structure could be understood in terms of groups of permutations acting on individual clauses in any particular Boolean theory. We conclude the series by discussing the techniques needed to implement our ideas, and by reporting on their performance on a variety of problem instances.

In this paper, we construct and investigate a hierarchy of spatio-temporal formalisms that result from various combinations of propositional spatial and temporal logics such as the propositional temporal logic PTL, the spatial logics RCC-8, BRCC-8, S4u and their fragments. The obtained results give a clear picture of the trade-off between expressiveness and `computational realisability' within the hierarchy. We demonstrate how different combining principles as well as spatial and temporal primitives can produce NP-, PSPACE-, EXPSPACE-, 2EXPSPACE-complete, and even undecidable spatio-temporal logics out of components that are at most NP- or PSPACE-complete.

Typically, translation algorithms from a symbolic to a connectionist representation and vice-versa are employed to provide either (i) a neural implementation of a logic, (ii) a logical characterisation of a neural system, or (iii) a hybrid learning system that brings together features from connectionism and symbolic artificial intelligence (Holldobler, 1993). Until recently, neural-symbolic systems were not able to fully represent, reason and learn expressive languages other than propositional and fragments of first-order logic (Cloete & Zurada, 2000). However, in (d'Avila Garcez et al., 2002b; d'Avila Garcez et al., 2002c; d'Avila Garcez et al., 2003), a new approach to knowledge representation and reasoning in neural-symbolic systems based on neural networks ensembles has been introduced. This new approach shows that modal logics can be effectively represented in artificial neural networks. In this paper, following the approach introduced in (d'Avila Garcez et al., 2002b; d'Avila Garcez et al., 2002c; d'Avila Garcez et al., 2003), we move one step further and show that temporal logics can be effectively represented in artificial neural o Artur Garcez is partly supported by the Nuffield Foundation. Luis Lamb is partly supported by CNPq. The authors would like to thank the referees for their comments.

Typically, translation algorithms from a symbolic to a connectionist representation and vice-versa are employed to provide either (i) a neural implementation of a logic, (ii) a logical characterisation of a neural system, or (iii) a hybrid learning system that brings together features from connectionism and symbolic artificial intelligence (Holldobler, 1993). Until recently, neural-symbolic systems were not able to fully represent, reason and learn expressive languages other than propositional and fragments of first-order logic (Cloete & Zurada, 2000). However, in (d'Avila Garcez et al., 2002b; d'Avila Garcez et al., 2002c; d'Avila Garcez et al., 2003), a new approach to knowledge representation and reasoning in neural-symbolic systems based on neural networks ensembles has been introduced. This new approach shows that modal logics can be effectively represented in artificial neural networks. In this paper, following the approach introduced in (d'Avila Garcez et al., 2002b; d'Avila Garcez et al., 2002c; d'Avila Garcez et al., 2003), we move one step further and show that temporal logics can be effectively represented in artificial neural o Artur Garcez is partly supported by the Nuffield Foundation. Luis Lamb is partly supported by CNPq. The authors would like to thank the referees for their comments.

Typically, translation algorithms from a symbolic to a connectionist representation and vice-versa are employed to provide either (i) a neural implementation of a logic, (ii) a logical characterisation of a neural system, or (iii) a hybrid learning system that brings together features from connectionism and symbolic artificial intelligence (Holldobler, 1993). Until recently, neural-symbolic systems were not able to fully represent, reason and learn expressive languages other than propositional and fragments of first-order logic (Cloete & Zurada, 2000). However, in (d'Avila Garcez et al., 2002b; d'Avila Garcez et al., 2002c; d'Avila Garcez et al., 2003), a new approach to knowledge representation and reasoning in neural-symbolic systems based on neural networks ensembles has been introduced. This new approach shows that modal logics can be effectively represented in artificial neural networks. In this paper, following the approach introduced in (d'Avila Garcez et al., 2002b; d'Avila Garcez et al., 2002c; d'Avila Garcez et al., 2003), we move one step further and show that temporal logics can be effectively represented in artificial neural o Artur Garcez is partly supported by the Nuffield Foundation. Luis Lamb is partly supported by CNPq. The authors would like to thank the referees for their comments.

(Niles and Pease 2001). Considering that tremendous scheduling that are robust in the face of realworld progress has been made in commonsense reasoning concerns like time zones, daylight savings in specialized topics such as thermodynamics time, and international calendar variations. in physical systems (Collins and Forbus 1989), it is surprising that our best content theories Given the importance of an ontology of of people are still struggling to get past time across so many different commonsense simple notions of belief and intentionality (van der Hoek and Wooldridge 2003). However, search is the generation of competency theories systems that can successfully reason about that have a degree of depth necessary to solve people are likely to be substantially more valuable inferential problems that people are easily able than those that reason about thermodynamics to handle. in most future applications. Yet competency in content theories is only Content theories for reasoning about people half of the challenge. Commonsense reasoning are best characterized collectively as a theory of in AI theories will require that computers not commonsense psychology, in contrast to those only make deep humanlike inferences but also that are associated with commonsense (naïve) ensure that the scope of these inferences is as physics. The scope of commonsense physics, broad as humans can handle, as well. That is, best outlined in Patrick Hayes's first and second in addition to competency, content theories will "Naïve Physics Manifestos" (Hayes 1979, need adequate coverage over the full breadth of 1984), includes content theories of time, space, concepts that are manipulated in human-level physical entities, and their dynamics. It is only by achieving psychology, in contrast, concerns all some adequate level of coverage that we of the aspects of the way that people think they can begin to construct reasoning systems that think. It should include notions of plans and integrate fully into real-world AI applications, goals, opportunities and threats, decisions and where pragmatic considerations and expressive preferences, emotions and memories, along user interfaces raise the bar significantly.