The background of the presentation is a perspective on the development of wireless technology from 2000 to 2010. The foreground of the presentation is a contrasted understanding of intelligence in "natural" wireless (human communication) versus "artificial" wireless (communication between devices). Invited talk, presented at The Twelfth Annual Conference on Innovative Applications of Artificial Intelligence (IAAI-2000), Austin, TX, August, 2000.

First appeared asRussell, S. J., Subramanian, D., and Parr, R. , "Provably bounded optimal agents", IJCAI-93, pp. 338-€“345. Journal of Artificial Intelligence Research, 1 (1995), pp.1-36.

Phil. Trans. R. Soc. Lond. A. 1994 349 1689. Intelligence is a complex, natural phenomenon exhibited by humans and many other living things, without sharply defined boundaries between intelligent and unintelligent behaviour. Artificial inteliigence focuses on the phenomenon of intelligent behaviour, in humans or machines. Experimentation with computer programs allows us to manipulate their design and intervene in the environmental conditions in ways that are not possible with humans. Thus, experimentation can help us to understand what principles govern intelligent action and what mechanisms are sufficient for computers to replicate intelligent behaviours.

This book (originally published in 1994 by Ellis Horwood) is now out of print. The copyright now resides with the editors who have decided to make the material freely available on the web.This book is based on the EC (ESPRIT) project StatLog which compare and evaluated a range of classification techniques, with an assessment of their merits, disadvantages and range of application. This integrated volume provides a concise introduction to each method, and reviews comparative trials in large-scale commercial and industrial problems. It makes accessible to a wide range of workers the complex issue of classification as approached through machine learning, statistics and neural networks, encouraging a cross-fertilization between these discplines.

Best-first search is a general heuristic search algorithm that always expands next a frontier node of lowest cost. It includes as special cases breadth-first search, Dijkstra's single-source shortest-path algorithm, and the A∗ algorithm. Its applicability, however, is limited by its exponential memory requirement. Previous approaches to this problem, such as iterative deepening, do not expand nodes in best-first order if the cost function can decrease along a path. We present a linear-space best-first search algorithm (RBFS) that always explores new nodes in best-first order, regardless of the cost function, and expands fewer nodes than iterative deepening with a nondecreasing cost function. On the sliding-tile puzzles, RBFS with a nonmonotonic weighted evaluation function dramatically reduces computation time with only a small penalty in solution cost.

A short overview of artificial intelligence and its relationship with fuzzy logic is provided. We emphasize the role fuzzy logics can play in extending some of the models of Artificial Intelligence.

This paper presents a simple framework for Horn-clause abduction, with probabilities associated with hypotheses. The framework incorporates assumptions about the rule base and independence assumptions amongst hypotheses. It is shown how any probabilistic knowledge representable in a discrete Bayesian belief network can be represented in this framework. The main contribution is in finding a relationship between logical and probabilistic notions of evidential reasoning. This provides a useful representation language in its own right, providing a compromise between heuristic and epistemic adequacy. It also shows how Bayesian networks can be extended beyond a propositional language.

It is known that exact computation of conditional probabilities in belief networks is NP-hard. Many investigators in the AI community have tacitly assumed that algorithms for performing approximate inference with belief networks are of polynomial complexity. Indeed, special cases of approximate inference can be performed in time polynomial in the input size. However, we have discovered that the general problem of approximating conditional probabilities with belief networks, like exact inference, resides in the NP-hard complexity class. We develop a complexity analysis to elucidate the difficulty of approximate probabilistic inference.

Serial search algorithms often exhibit exponential run times and may require an exponential amount of storage as well. Thus, the design of parallel search algorithms with limited memory is of obvious interest. This paper presents an efficient SIMD parallel algorithm, called IDPS (for iterative-deepening parallel search). At a broad level IDPS is a parallel version of IDA∗. While generically we have called our algorithm an IDPS, performance of four variants of it has been studied through experiments conducted on the well-known test-bed problem for search algorithms, namely the Fifteen Puzzle.

Many modern grammatical formalisms divide the task of linguistic specification into a context free component of phrasal constraints and a separate component of attribute-value or functional constraints. Conventional methods for recognizing the strings of a language also divide into two parts so that they can exploit the different computational properties of these components. This paper focuses on the interface between these components as a source of computational complexity distinct from the complexity internal to each. We first analyze the common hybrid strategy in which a polynomial context-free parser is modified to interleave functional constraint solving with context-free constituent analysis. This strategy depends on the property of monotonicity in order to prune unnecessary computation.