We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the process of proving that certain planning problems are complete for NP^PP, we introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.

Review of Foundations of Cognitive Science

Most human-computer interfaces can be classified according to two dominant metaphors: (1) agent and (2) environment. In the environment metaphor, a model of the task domain is presented for the user to interact with directly. Norman's 1984 model of HCI is introduced as reference to organize and evaluate research in human-agent interaction (HAI). A wide variety of heterogeneous research involving HAI is shown to reflect automation of one of the stages of action or evaluation within Norman's model.

In the last few years, we have witnessed a major growth in the use of empirical methods in AI. In part, this growth has arisen from the availability of fast networked computers that allow certain problems of a practical size to be tackled for the first time. There is also a growing realization that results obtained empirically are no less valuable than theoretical results. I identify some of the emerging trends in this area by describing a recent workshop that brought together researchers using empirical methods as far apart as robotics and knowledge-based systems.

The Association for the Advancement of Artificial Intelligence held its 1997 Fall Symposia Series on 7 to 9 November in Cambridge, Massachusetts. This article contains summaries of the six symposia that were conducted: (1) Communicative Action in Humans and Machines, (2) Context in Knowledge Representation and Natural Language, (3) Intelligent Tutoring System Authoring Tools, (4) Model-Directed Autonomous Systems, (5) Reasoning with Diagrammatic Representations II, and (6) Socially Intelligent Agents.

In computational cognitive modeling, we hypothesize internal mental processes of human cognitive activities and express such activities by computer programs. Such computational models often consist of many components and aspects. Claims are often made that certain aspects play a key role in modeling, but such claims are sometimes not well justified or explored. We then discuss, in principle, systematic ways of identifying the source of power in models.

The 1997 AAAI Workshop on AI Approaches to Fraud Detection and Risk Management brought together over 50 researchers and practitioners to discuss problems of fraud detection, computer intrusion detection, and risk scoring. This article presents highlights, including discussions of problematic issues that are common to these application domains, and proposed solutions that apply a variety of AI techniques.

Much of our intelligence derives from our ability to manipulate our environment through collaborative endeavors. Most extant computer programs and interfaces do little to take advantage of such manifestly human talents and interests, leaving broad avenues of human-computer communication unexplored. In this article, we look at a number of autonomous agent systems that embody their intelligence at least partially through the projection of a believable, engaging, synthetic persona. Among other topics, we touch briefly on samples of research that explore synthetic personality, representations of emotion, societies of fanciful and playful characters, intelligent and engaging automated tutors, and users projected as avatars into virtual worlds.

Agent-based systems technology has generated lots of excitement in recent years because of its promise as a new paradigm for conceptualizing, designing, and implementing software systems. Currently, the great majority of agent-based systems consist of a single agent. Central to the design and effective operation of such multiagent systems (MASs) are a core set of issues and research questions that have been studied over the years by the distributed AI community. In this article, I present some of the critical notions in MASs and the research work that has addressed them.