Most of the emphasis in path planning, a topic of much interest in several domains, has been on finding the optimal path or at most k optimal paths. However, in domains such as adversarial planning, one of the agents might deliberately take less optimal paths to confuse the opponent, and by the same token an agent, for inferring opponent's intent, has to consider all possible paths that the opponent might take. We introduce the notion of representative paths in free space (2D) and study the problem of computing all representative paths with different properties, such as all representative paths with at most L loops, among polygonal regions using a framework of Voronoi diagram. We prove three properties: (1) the upper and lower bounds to the number of simple paths in a Voronoi graph (2) given any path, a homotopic path can always be obtained from the Voronoi diagram of the regions and (3) all representative paths with a given property might not be always obtainable from the Voronoi graph even after searching the graph exhaustively and present an algorithm to work around this limitation. We also show how our findings can be applied for efficient entity re-identification, a problem involving a large number of dynamic entities and obstacles in the military domain.

Diagrammatic reasoning (DR) is pervasive in human problem solving as a powerful adjunct to symbolic reasoning based on language-like representations. The research reported in this paper is a contribution to building a general purpose DR system as an extension to a SOAR-like problem solving architecture. The work is in a framework in which DR is modeled as a process where subtasks are solved, as appropriate, either by inference from symbolic representations or by interaction with a diagram, i.e., perceiving specified information from a diagram or modifying/creating objects in a diagram in specified ways according to problem solving needs. The perceptions and actions in most DR systems built so far are hand-coded for the specific application, even when the rest of the system is built using the general architecture. The absence of a general framework for executing perceptions/actions poses as a major hindrance to using them opportunistically -- the essence of open-ended search in problem solving. Our goal is to develop a framework for executing a wide variety of specified perceptions and actions across tasks/domains without human intervention. We observe that the domain/task-specific visual perceptions/actions can be transformed into domain/task-independent spatial problems. We specify a spatial problem as a quantified constraint satisfaction problem in the real domain using an open-ended vocabulary of properties, relations and actions involving three kinds of diagrammatic objects -- points, curves, regions. Solving a spatial problem from this specification requires computing the equivalent simplified quantifier-free expression, the complexity of which is inherently doubly exponential. We represent objects as configuration of simple elements to facilitate decomposition of complex problems into simpler and similar subproblems. We show that, if the symbolic solution to a subproblem can be expressed concisely, quantifiers can be eliminated from spatial problems in low-order polynomial time using similar previously solved subproblems. This requires determining the similarity of two problems, the existence of a mapping between them computable in polynomial time, and designing a memory for storing previously solved problems so as to facilitate search. The efficacy of the idea is shown by time complexity analysis. We demonstrate the proposed approach by executing perceptions and actions involved in DR tasks in two army applications.

Spatial problems (SP) are inevitable in reasoning with diagrams. In this paper, we investigate general representations and computational strategies for a SP-solver such that it can accept problems from a human in a high-level language and output the solution without human intervention. We propose a language in which a variety of domain- independent 2D SPs can be specified in terms of constraints. The constraints are specified in first-order logic over the real domain using a vocabulary of objects, properties, relations and actions. We also propose two general and independent computational strategies - constraint satisfaction and spatial search - for autonomously solving the SPs. Ideas about how to make these strategies computationally efficient are discussed and illustrated by examples.

Advances in commodity processor and network technologies have made cluster-based servers very attractive for supporting a large number of interactive applications (such as visualization and data mining) in the domains of Grid computing and distributed computing. These applications involve accesses to huge amounts of data within the servers and heavy computations on the accessed data before sending out the results to the clients. The interactive nature of these applications requires some kind of QoS support (such as guarantees on response time) from the underlying server. Unfortunately, the current generation cluster-based servers with the popular interconnect (Gigabit Ethernet, Myrinet, or Quadrics) do not provide any kinds of QoS support. Fortunately, many of these applications are resource-adaptive, i.e., application parameters can be changed to suit user demands and available system resources. To solve these problems, a new QoS-aware middleware layer is proposed in this paper for cluster-based servers with Myrinet interconnect. The middleware is built on top of a simple NIC-based rate control scheme that provides proportional bandwidth allocation. Three major components of the middleware (profiler, QoS translator, and resource allocator), their functionalities, designs, and the associated algorithms are presented. These components work together to execute a requested job in a predictable manner with an efficient allocation of system resources while exploiting the resource-adaptive property of the application. The complete middleware is designed, developed, and implemented on a Myrinet cluster. It is evaluated for two visualization applications: polygon rendering and ray-tracing. Experimental evaluations demonstrate that the proposed QoS framework enables multiple interactive and resource-adaptive applications to be executed in a predictable manner while keeping the allocation of system resources efficient. It is shown that the QoS-aware middleware helps applications to obtain response times within 7% of the expected times, compared to increases of up to 117% in the absence of any QoS support.

In this paper, we present a comprehensive performance comparison of MPI implementations over Infini-Band, Myrinet and Quadrics. Our performance evaluation consists of two major parts. The first part consists of a set of MPI level micro-benchmarks that characterize different aspects of MPI implementations. The second part of the performance evaluation consists of application level benchmarks. We have used the NAS Parallel Benchmarks and the sweep3D benchmark. We not only present the overall performance results, but also relate application communication characteristics to the information we acquired from the micro-benchmarks. Our results show that the three MPI implementations all have their advantages and disadvantages. For our 8-node cluster, InfiniBand can offer significant performance improvements for a number of applications compared with Myrinet and Quadrics when using the PCI-X bus. Even with just the PCI bus, InfiniBand can still perform better if the applications are bandwidth-bound.

Careful study of medical informatics research and library-resource projects is necessary to increase the productivity of the research and development enterprise. Medical informatics research projects can present unique problems with respect to evaluation. It is not always possible to adapt directly the evaluation methods that are commonly employed in the natural and social sciences. Problems in evaluating medical informatics projects may be overcome by formulating system development work in terms of a testable hypothesis; subdividing complex projects into modules, each of which can be developed, tested and evaluated rigorously; and utilizing qualitative studies in situations where more definitive quantitative studies are impractical.

The concept of the generic task, one of a small set of ubiquitous cognitive tasks that together account for some part of human cognition, is examined. In particular, how hierarchical classification is one such generic task and how it is useful for diagnosis is shown. It is also shown that a diagnosis system based on hierarchical classification naturally lends itself to solving a number of issues traditionally associated with sensor validation is examined.>

The general information-processing task of classification is considered and reviewed from the perspectives of the knowledge-based-reasoning, pattern-recognition, and connectionist paradigms in artificial intelligence, paying special attention to knowledge-based classificatory problem solving. The authors trace the evolution of the mechanisms for classification as the computational complexity of the problem increases, from numerical parameter-setting schemes, through those using intermediate abstractions and then relations between symbols, and finally to complex symbolic structures that explicitly incorporate domain knowledge.>

A general problem-solving mechanism is described that is especially suited for performing a particular form of abductive inference, or best explanation finding. A problem solver embodying this mechanism synthesizes composite hypotheses by combining simple hypotheses to satisfy explanatory goals. These simple hypotheses are formed by instantiating prestored explanatory "concepts." In this way the problem solver is able to arrive at complex integrated conclusions which are not prestored. A computationally feasible task-specific problem-solving mechanism is presented for a particular information-processing task which is, nevertheless, of very great generality. The task is that of synthesizing coherent composite explanatory hypotheses based upon a prestored and possibly vast collection of hypothesis-generating concepts. This is seemingly a common task of intelligence and potentially a major component of diagnostic reasoning, especially where single-fault assumptions are inappropriate. The mechanism is described both functionally and structurally; that is, the why and what of the main computations are described, together with algorithms that show how each of these computations can be accomplished. The mechanism integrates a classification machine, used for selecting plausible hypotheses, with a specialized means-ends machine, used for assembling a best explanation from the plausible hypotheses thus selected and for pointedly investigating alternative explanations. There are also two other specialized mechanisms for the subsidiary functions of recognizing the applicability of a hypothesis to the situation and of interpreting the situation-specific raw data to satisfy the informational needs of the other components.

Naturally occurring information systems provide a number of useful metaphors for distributed problem solving. An introduction to some aspects of these metaphors is given which simultaneously serves as a guest editorial for a special issue devoted to the topic. The ubiquity of a distributed mode of computation in information processing in natural phenomena in general and in human societies in particular is observed and related to the evolutionary and complexity-reducing advantages of this mode. The forms of communication media available to coordinate the problem solving activities of the individual processors are examined. Some general remarks are made on how problem solving is distributed and coordinated in some human organizations, and the potential usefulness of the " society of specialists" notion in explicating cognitive activity is pointed out. Along the way, the contents of the papers in the special issue are considered in relation to various points raised in the discussion.

A diagnostician, when he arrives at a diagnosis or diagnoses, has invoked some concepts. They can be diseases, causes of them, or other notions that are relevant to the diagnosis. These concepts form a hierarchical structure similar to a botanical or zoological classification. The diagnostician's knowledge is distributed through this hierarchy. The concepts in the hierarchy provide the criteria to organize under them small pieces of knowledge represented in the form of production rules. Thus concepts may be viewed as clusters of production rules. They extend the capabilities of production rules to more complex problem solving situations. The rules under each concept are further organized into three subgroups: exclusionary, confirmatory, and recommendation rules. During the problem solving process, the concepts are taken as specialists. They interact and communicate among themselves by means of a blackboard.

THIS special collection had its genesis at the IEEE Computer Society Workshop on Software Testing and Test Documentation, held in Fort Lauderdale, Florida, during December 18-20, 1978. This collection is devoted to selected papers on program testing that were presented at the Workshop. It contains six papers whose concerns span a wide range: theoretical issues, practical expenence With particular strategies, extension of a class of techniques to new classes of language constructs, and building integrated test tools. In the next section, we present an overview of the papers in the collection.

The design of optimal, time-invariant, randomized, finite-state automata forK-hypothesis testing is an open problem forK > 2. A lower bound is constructed on the smallest probability of error achievable bym-state automata solving a three-hypothesis Bernoulli problem. A class of close-to-optimal automata is exhibited that requires at most one extra bit of memory to match the performnnce of an optimal automaton.

The least upper bound on the asymptotic proportion of the choice of the correct coin, achievable by {\em expedient} finite-memory algorithms in certain two-armed bandit problems, is derived and schemes which achieve these bounds in a limiting sense are displayed. A deterministic automaton whose performance is close to optimal is also presented.

A class of irreducible deterministic finite-memory algorithms for the symmetric hypothesis testing problem is studied. It is shown how members of this class can be constructed to give a steady-state probability of error that decreases asymptotically faster in the number of states than the best previously known deterministic algorithm.

If f(x) and g(x) are the densities for the N-dimensional measurement vector x, conditioned on the classes c1and c2, and if finite sets of samples from the two classes are available, then a decision function based on estimates f(x) and ĝ(x) can be used to classify future observations. In general, however, when the measurement complexity (the dimensionality N) is increased arbitrarily and the sets of training samples remain finite, a ''peaking phenomenon'' of the following kind is observed: classification accuracy improves at first, peaks at a finite value of N, called the optimum measurement complexity, and starts deteriorating thereafter. We derive, for the case of statistically independent measurements, general conditions under which it can be guaranteed that the peaking phenomenon will not occur, and the correct classification probability will keep increasing to value unity as N → ∞. Several applications are considered which together indicate, contrary to general belief, that independence of measurements alone does not guarantee the absence of the peaking phenomenon.

It is known that, in general, the number of measurements in a pattern classification problem cannot be increased arbitrarily, when the class-conditional densities are not completely known and only a finite number of learning samples are available. Above a certain number of measurements, the performance starts deteriorating instead of improving steadily. It was earlier shown by one of the authors that an exception to this "curse of finite sample size" is constituted by the case of binary independent measurements if a Bayesian approach is taken and uniform a priori on the unknown parameters are assumed. In this paper, the following generalizations are considered: arbitrary quantization and the use of maximum likelihood estimates. Further, the existence of an optimal quantization complexity is demonstrated, and its relationship to both the dimensionality of the measurement vector and the sample size are discussed. It is shown that the optimum number of quantization levels decreases with increasing dimensionality for a fixed sample size, and increases with the sample size for fixed dimensionality.

Almost all of the published work on the philosophical question of the limitation of mechanical intelligence has argued in favor of one or the other of the polarities of possible positions, those of the True Believer and the Infidel. It is, however, possible to take a position between these two extremes, a position we call Agnostic. We believe agnosticism concerning the possibility of artificial intelligence to be a position held by many computer scientists. In general, the True Believer maintains that "thinking" machines are "just around the corner," while the Infidel maintains that, for one reason or another, such machines are impossible. The Agnostic is willing to accept the mechanist thesis, but he feels that the relevant question for artificial intelligence research is whether it is possible to design an intelligent machine. Much of the argument between the Agnostic and the True Believer hinges on the complexity of the system to be simulated. The latter holds that man "as a behaving system" cannot be so complex as to be practically beyond design. The Agnostic holds that the mind may be "simply" a machine, but it is not a simple machine. Furthermore, there is the problem of the complexity of the procedure required to unravel the structure of a system. Even if there is agreement on the internal complexity of the mind, the question as to the complexity of the diagnostic procedure required to identify its structure remains open. Our agnosticism is one of belief, not of action.

A situation of great practical importance in pattern recognition is the case where the designer has only a finite number of sample patterns from each class and the class-conditional density functions are not completely known. Recent results indicate that in this case the dimensionality of the pattern vector, i.e., the number of measurements, should not be arbitrarily increased, since above a certain value (corresponding to the optimal measurement complexity), the performance starts to deteriorate instead of improving steadily. However, whether this phenomenon occurs in the case of independent measurements has been an open question until now. In this paper the following result of practical importance is derived. When the measurements are independent, and a Bayesian approach is taken, one can add extra measurements without fear of this peaking of performance; i.e., the optimal measurement complexity is infinite. In fact, under certain conditions, having just one sample from class 1, and none at all from class 2, can result in a recognition accuracy arbitrarily close to unity for a large enough number of measurements. The implication of these results to practice is discussed, along with the general question of dimensionality and sample size.

In this correspondence, we critically examine some recent papers that attempt to obtain optimal finite-memory solutions for some hypothesis-testing problems. We point out that these solutions contain hidden memory-consuming elements, and hence are not optimal. We present and examine various possible definitions of finite memory from a finite-state-machine viewpoint.