Search

We have proposed about an image template generation method for the self-position estimation of an autonomous mobile robot based on anytime algorithm. In this method, the time for the self-position estimation can be varied by changing the size of image templates. Moreover, the stable self-position estimation can be realized even if the size of image templates is changed. However, image templates are generated with genetic algorithm in this method. Therefore, the time for the template generation is enormous. In this paper, we propose a new image template generation method based on genetic algorithm with the fitness inference system to reduce the template generation time. In our method, the values of some parameters in the evaluation function are inferred instead of inferring the evaluation value directly. Then, the evaluation value are calculated with the inferred parameters by using the evaluation function. The time for the image template generation can be reduced drastically by the proposed method. The usefulness of the image templates generated by the proposed method is shown through some experimental results of the self-position estimation using a real- robot.

Due to the growing complexity and adaptability requirements of real-time embedded systems, which often exhibit unrestricted inter-dependencies among supported services and user-imposed quality constraints, it is increasingly difficult to optimise the level of service of a dynamic task set within an useful and bounded time. This is even more difficult when intending to benefit from the full potential of an open distributed cooperating environment, where service characteristics are not known beforehand. This paper proposes an iterative refinement approach for a service’s QoS configuration taking into account services’ inter-dependencies and quality constraints, and trading off the achieved solution’s quality for the cost of computation. Extensive simulations demonstrate that the proposed anytime algorithm is able to quickly find a good initial solution and effectively optimises the rate at which the quality of the current solution improves as the algorithm is given more time to run. The added benefits of the proposed approach clearly surpass its reduced overhead.

In this paper, an anytime algorithm based on the modified genetic algorithm (GA) is presented to solve the dynamic weapon-target allocation (DWTA) problem. With this algorithm, the targets are assigned with weapons one-by-one according to when each target flies away from the launching zone of the weapons, which is also a deadline for completion of pairing weapon for the target. In this paper, the modified GA is applied to the case that the targets are reduced by continuous interception until all of them are neutralized, and along with it in the process, the number of weapons put in use is decreasing. This is a marginal case for an integrated DWTA problem, and the investigation on it provides a basis for solving more complex DWTA problem.

An anytime algorithm based on modified genetic algorithm (GA) for dynamic WTA problem, subject to temporal constraints, is developed in the paper. In the algorithm the weapons are assigned to targets one by one before the deadline of each target comes. After a target is assigned with some weapon, the target is replaced by a new one in all chromosomes in the population while the optimization process will not undergo any restart. The algorithm has three main advantages: 1) a new target can be dynamically accommodated in the allocation process without losing previous optimizing information, 2) the quality of the pairing decisions may be improved in the evolving process with a prolonged computation time, and 3) it optimally deploys weapons to targets where a weapon can be assigned to more than one target asynchronously without missing any deadline of the targets, under the precondition that the weapon can be allocated to only one target at one time. The feasibility and the validity of the modified GA are verified in simulations.

We propose a new approximate algorithm, LA- JIV (lookahead J-MDP information value), to solve oracular partially observable Markov decision problems (OPOMDPs), a special type of POMDP that rather than standard observations includes an "oracle" that can be consulted for full state information at a fixed cost. We previously introduced JIV (J-MDP information value) to solve OPOMDPs, an heuristic algorithm that utilizes the solution of the underlying MDP and weighs the value of consulting the oracle against the value of taking a state-modifying action. While efficient, JIV will rarely find the optimal solution. In this paper, we extend JIV to include lookahead, thereby permitting arbitrarily small deviation from the optimal policy's long-term expected reward at the cost of added computation time. The depth of the lookahead is a parameter that governs this tradeoff; by iteratively increasing this depth, we provide an anytime algorithm that yields an ever- improving solution. LA-JIV leverages the OPOMDP framework's unique characteristics to outperform general-purpose approximate POMDP solvers; in fact, we prove that LA-JIV is a poly-time approximation scheme (PTAS) with respect to the size of the state and observation spaces, thereby showing rigorously that OPOMDPs are "easier" than POMDPs. Finally, we substantiate our theoretical results via an empirical analysis of a benchmark OPOMDP instance.

The phenomenon of self-organization has been of special interest to the neural network community throughout the last couple of decades. In this paper, we study a variant of the self-organizing map (SOM) that models the phenomenon of self-organization of the particles forming a string when the string is tightened from one or both of its ends. The proposed variant, called the string tightening self-organizing neural network (STON), can be used to solve certain practical problems, such as computation of shortest homotopic paths, smoothing paths to avoid sharp turns, computation of convex hull, etc. These problems are of considerable interest in computational geometry, robotics path-planning, artificial intelligence (AI) (diagrammatic reasoning), very large scale integration (VLSI) routing, and geographical information systems. Given a set of obstacles and a string with two fixed terminal points in a 2-D space, the STON model continuously tightens the given string until the unique shortest configuration in terms of the Euclidean metric is reached. The STON minimizes the total length of a string on convergence by dynamically creating and selecting feature vectors in a competitive manner. Proof of correctness of this anytime algorithm and experimental results obtained by its deployment have been presented in the paper.

Many perceptual grouping algorithms depend on parameters one way or another. It is always difficult to set these parameters appropriately for a wide range of input images, and parameters tend to be tuned to a small set of test cases. Especially certain thresholds often seem unavoidable to limit search spaces in order to obtain reasonable runtime complexity. Furthermore early pruning of less salient hypotheses is often necessary to avoid exponential growth of the number of hypotheses. In the presented work we show how the adoption of a simple anytime algorithm, i. e. an algorithm which returns the best answer possible when interrupted and may improve on the answer if allowed to run longer, for finding closed convex polygons eliminates the need for parameter tuning. Furthermore it quite naturally allows the incorporation of attentional mechanisms into the grouping process.

In most real-world applications the choice of the right representation language represents a fundamental issue, since it may give opportunities for generalization and make inductive reasoning computationally easier or harder. While the setting of First Order Logic (FOL) is the most suitable one to model the multi-relational data of real and complex domains, on the other hand it puts the question of the computational complexity of the knowledge induction that represents a challenge for multi-relational data mining algorithms. Indeed, the complexity of most real domains, in which a lot of relationships are required to model the objects involved, calls for both an efficient and effective search method for exploring the space of candidate solutions and a deduction procedure assessing the validity of the discovered knowledge. A way of tackling the complexity of such domains is to use a method that reformulates a multi-relational learning task into an attribute-value one. In this paper we propose an approximate reasoningtechnique that decreases the complexity of a relational problem changing both the language and the inference operation used for the deduction. The complexity of the FOL language is decreased by means of a stochastic propositionalization method, while the NP-completeness of the deduction is tackled using an approximate query evaluation. The induction is performed with an anytime algorithm, implemented by a population based method, able to efficiently extract knowledge from structured data in form of complete FOL definitions. The validity of the proposed technique has been proved making an empirical evaluation on a real-world dataset.

The QoS-aware web service composition WSC problem constructs a composite web service with the optimal accumulated QoS value. In the real world, this problem encounters some challenges. First, while most QoS-aware WSC techniques make their decisions based on the QoS information published by each service provider, the actual QoS performance at run-time may be inconsistent with the QoS specification due to the dynamic execution environment and intentional/unintentional error in the QoS declaration. Another obstacle is that the QoS-aware WSC problem for large scale instances is intractable to solve since the problem corresponds to a global optimisation problem. Toward these challenges, we propose a novel QoS-aware WSC method based on the real service transaction history of web services, which employs the anytime algorithm technique. In the experiment, our proposal can deal with the uncertain QoS efficiently and identify composite web services with high quality much earlier than the optimal algorithm.

Clustering is vital in the process of condensing and outlining information, since it can provide a synopsis of the stored data. However, the high dimensionality of multimedia data today presents an insurmountable challenge for clustering algorithms. Based on the well-known fact that time series and image histograms can both be represented accurately in a lower resolution using orthonormal decompositions, we present an anytime version of the k-means algorithm. The algorithm works by leveraging off the multiresolution property of wavelets. The dilemma of choosing the initial centers for k-means is mitigated by assigning the final centers at each approximation level as the initial centers for the subsequent, finer approximation. In addition to casting k-means as an anytime algorithm, our approach has two other very desirable properties. We observe that even by working at coarser approximations, the achieved quality is better than the batch algorithm, and that even if the algorithm is run to completion, the running time is significantly reduced. We show how this algorithm can be suitably extended to chromatic and textural features extracted from images. Finally, we demonstrate the applicability of this approach on the online image search engine scenario.

The problem of joint maximum a posteriori (MAP) bias estimation and data association belongs to a class of nonconvex mixed integer nonlinear programming problems. These problems are difficult to solve due to both the combinatorial nature of the problem and the nonconvexity of the objective function or constraints. A specific problem that has received some attention in the tracking literature is that of the target object map problem in which one tries match a set of tracks as observed by two different sensors in the presence of biases, which are modeled here as a translation between the track states. The general framework also applies to problems in which the costs are general nonlinear functions of the biases. The goal of this paper is to present a class of algorithms based on the branch and bound framework and the "all-pairs" and k-best heuristics that provide a good initial upper bound for a branch and bound algorithm. These heuristics can be used as part of a real-time algorithm or as part of an "anytime algorithm" within the branch and bound framework. In addition, we consider both the A*-search and depth-first search procedures as well as several efficiency improvements such as gating. While this paper focuses on the algorithms, a second paper will focus on simulations.

Coalition formation is a key topic in multiagent systems. One may prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow exhaustive search for the optimal one. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? Sandholm et al. showed that it suffices to search the lowest two levels of the coalition structure graph in order to establish a worst case bound K(n). Dang et al. presented an algorithm that takes a step further to search those coalition structures whose biggest coalition's cardinality is greater than or equal to ⌈n(k − 1)/(k + 1)⌉, which is the best result known so far. Against this background, this paper reports on a novel anytime algorithm based on cardinality structure that only have to take a step further to search those coalition structures whose cardinality structure is in the CCS(n, b). Consequently, the algorithm reported in this paper is obviously better than that of Sandholm et al. (up to 1035 times faster when n=100, K=2) and Dang et al (up to 1018 times faster when n=100, K=3).

Coordination, as a key issue in fully cooperative multiagent systems, raises a number of challenges. A crucial one among them is to efficiently find the optimal joint action in an exponential joint action space. Variable elimination offers a viable solution to this problem. Using their algorithm, each agent can choose an optimal individual action resulting in the optimal behavior for the whole agents. However, the worst-case time complexity of this algorithm grows exponentially with the number of agents. Moreover, variable elimination can only report an answer when the whole algorithm terminates. Therefore, it is unsuitable in real-time systems. In this paper, we propose an anytime algorithm, called the simulated annealing algorithm, as an approximation alternative to variable elimination. We empirically show that our algorithm can compute nearly optimal results with a small fraction of the time that variable elimination takes to find the solution to the same coordination problem.

For many real world problems we must perform classification under widely varying amounts of computational resources. For example, if asked to classify an instance taken from a bursty stream, we may have from milliseconds to minutes to return a class prediction. For such problems an anytime algorithm may be especially useful. In this work we show how we can convert the ubiquitous nearest neighbor classifier into an anytime algorithm that can produce an instant classification, or if given the luxury of additional time, can utilize the extra time to increase classification accuracy. We demonstrate the utility of our approach with a comprehensive set of experiments on data from diverse domains.

An automatic summarization system for local assembly minutes is described. Our system is unique in the following two points: First, the completeness that puts emphasis on the readability of the generated summary is realized. Secondly, the preference that prioritizes the selection based on the viewpoint on the content of the summary is considered. Our system has a t wo-level structure that brings about the property of "anytime algorithm": The neural network in the lower layer recollects important sentences based on the frequency of the words in the text. Then, based on the snapshot of the neural network, the summary gnerator in the upper layer extracts a cluster of sentences around the important sentences, with the prioritization by the user's preferred viewpoint. The effectiveness of our method is demonstrated using the actual minutes of a prefecture in Japan.

This paper describes quasi-online reinforcement learning: while a robot is exploring its environment, in the background a probabilistic model of the environment is built on the fly as new experiences arrive; the policy is trained concurrently based on this model using an anytime algorithm. Prioritized sweeping, directed exploration, and transformed reward functions provide additional speed-ups. The robot quickly learns goal-directed policies from scratch, requiring few interactions with the environment and making efficient use of available computation time. From an outside perspective it learns the behavior online and in real time. We describe comparisons with standard methods and show the individual utility of each of the proposed techniques

This paper proposes an adaptive scheduling method using anytime algorithm under such a condition that the processing time is restricted or is not enough. By using typical image processing procedure as an example, this paper discusses how to modify conventional image processing algorithms to anytime algorithmic image processing, modeling of time-precision function and an adaptive scheduling method to realize the maximum performance in the restricted time

This paper applies the Object Oriented Probabilistic Relational Modelling Language to recursive probability models. We present two novel anytime inference algorithms for recursive probability models expressed using this language. We discuss the strengths and limitations of these algorithms and compare their performance against the Iterative Structured Variable Elimination algorithm proposed for Probabilistic Relational Modelling Language using three different non-linear genetic recursive probability models.

The scarcity and diversity of resources among the devices of heterogeneous computing environments may affect their ability to execute services within the users' requested Quality of Service levels, particularly in open real-time environments where the characteristics of the computational load cannot always be predicted in advance but, nevertheless, response to events still has to be provided within precise timing constraints in order to guarantee a desired level of performance. This paper proposes a cooperative service execution, allowing resource constrained devices to collectively execute services with their more powerful neighbours, meeting non-functional requirements that otherwise would not be met by an individual execution. Nodes dynamically group themselves into a new coalition, allocating resources to each new service and establishing an initial service configuration which maximises the satisfaction of the QoS constraints associated with the new service and minimises the impact on the global QoS caused by the new service's arrival. However, the increased complexity of open real-time environments may prevent the possibility of computing optimal local and global resource allocations within a useful and bounded time. As such, the QoS optimisation problem is here reformulated as a heuristic-based anytime optimisation problem that can be interrupted at any time and quickly respond to environmental changes. Extensive simulations demonstrate that the proposed anytime algorithms are able to quickly find a good initial service solution and effectively optimise the rate at which the quality of the current solution improves at each iteration of the algorithms, with an overhead that can be considered negligible when compared against the introduced benefits.

We address the problem of building an integrated meta-level framework for time deliberation and parameter control for a system solving a set of hard problems. The trade-off is between the solution qualities achieved for individual problems and the global outcome under the given time-quality constraints. Each problem is modeled as an anytime optimization algorithm whose quality-time performance varies with different control parameter settings. We use the proposed meta-level strategy for generating a deliberation schedule and adaptive cooling mechanism for anytime simulated annealing (ASA) solving hard task sets. Results on task sets comprising of the traveling salesman problem (TSP) instances demonstrate the efficacy of the proposed control strategies.

Subject to limited computational resource, feedback scheduling aims to improve, or to optimize, the global control performance of real-time control systems. For the system that consists of simple control tasks, a feedback scheduling scheme is presented to shorten tasks' deadlines online as much as possible, so as to reduce jitter and to improve the performance. For the system that consists of complex control tasks, another feedback scheduling scheme is presented to adjust the reserved processor time for each task dynamically, and thus to optimize the performance, if these tasks can be implemented as anytime algorithm. The general feedback scheduling architecture is introduced. The control strategy in both schemes is model predictive control. The designs of feedback controllers are discussed. And the stability conditions are also analyzed.

Finding a minimal decision tree consistent with the examples is an NP-complete problem. Therefore, most of the existing algorithms for decision tree induction use a greedy approach based on local heuristics. These algorithms usually require a fixed small amount of time and result in trees that are not globally optimal. Recently, the LSID3 contract anytime algorithm was introduced to allow using extra resources for building better decision trees. A contract anytime algorithm needs to get its resource allocation a priori. In many cases, however, the time allocation is not known in advance, disallowing the use of contract algorithms. To overcome this problem, in this work we present two interruptible anytime algorithms for inducing decision trees. Interruptible anytime algorithms do not require their resource allocation in advance and thus must be ready to be interrupted and return a valid solution at any moment. The first interruptible algorithm we propose is based on a general technique for converting a contract algorithm to an interruptible one by sequencing. The second is an iterative improvement algorithm that repeatedly selects a subtree whose reconstruction is estimated to yield the highest marginal utility and rebuilds it with higher resource allocation. Empirical evaluation shows a good anytime behavior for both algorithms. The iterative improvement algorithm shows smoother performance profiles which allow more refined control.

Wireless sensor networks (WSN) are envisioned to consist of large numbers of minimum capacity devices operating in demanding real-world environments. These issues, together with the inherent problems of wireless communication, make security an especially difficult problem. Many WSN also need to operate under real-time constraints. We discuss three routing protocols for WSN that have good real-time performance properties: SPEED, RAP and IGF. We suggest extensions to these protocols that improve their security properties. Denial of service is another key problem facing WSN. We discuss a highly decentralized algorithm for the detection and mapping of jammed regions of a WSN. The solution is robust to failures and can operate on partial information (a type of anytime algorithm). We conclude by considering several potential future directions for security solutions, including: secure groups based on relaxed semantics, exploiting physical properties, exploiting time validity intervals for data, and the interaction between security and privacy.

This project addressed the problem of the real-time management of distributed resources. It developed an abstract formulation in terms of distributed constraint optimization and developed a simple anytime algorithm that was shown to be effective efficient robust and scalable to large problems. It extended the formulation and algorithm to the management of distributed sensors in a target detection and tracking application. It also developed high-level models for resource management in time-critical targeting in air campaigns and extended an existing scheduler generator tool to automatically generate executable schedulers that quickly assign aircraft and munitions to prosecute targets of opportunity while minimizing disruption to pre-planned target prosecutions.

The problem of interpreting Natural Language (NL) discourse is generally of exponential complexity. However, since interactions with users must be conducted in real time, an exhaustive search is not a practical option. In this paper, we present an anytime algorithm that generates "good enough" interpretations of probabilistic NL arguments in the context of a Bayesian network (BN). These interpretations consist of: BN nodes that match the sentences in a given argument, assumptions that justify the beliefs in the argument, and a reasoning structure that adds detail to the argument. We evaluated our algorithm using automatically generated arguments and hand-generated arguments. In both cases, our algorithm generated good interpretations (and often the best interpretation) in real time.

There are some problems in which the time required for evaluating a Bayesian network must not be long. This means that not all the propagation algorithms could be applied in these situations, and therefore an appropriate method must be chosen. A type of evaluation that fulfills this requirement is known generically as “anytime algorithm”. They are able to return an approximate output at any moment, solution that could be enough for some problems. In this paper two methods framed in this approach are presented. These are modifications of the Pearl’s exact propagation algorithm for singly connected networks, designed with the final aim of reducing the propagation effort in domain problems where the number of variables is very large and the domain knowledge could be represented using that topology. As a very suitable test bed for measuring their quality, the field of Information Retrieval was selected. Results of a detailed experimentation are presented as well, showing a good performance.

Several important time series data mining problems reduce to the core task of finding approximately repeated subsequences in a longer time series. In an earlier work, we formalized the idea of approximately repeated subsequences by introducing the notion of time series motifs. Two limitations of this work were the poor scalability of the motif discovery algorithm, and the inability to discover motifs in the presence of noise.Here we address these limitations by introducing a novel algorithm inspired by recent advances in the problem of pattern discovery in biosequences. Our algorithm is probabilistic in nature, but as we show empirically and theoretically, it can find time series motifs with very high probability even in the presence of noise or "don't care" symbols. Not only is the algorithm fast, but it is an anytime algorithm, producing likely candidate motifs almost immediately, and gradually improving the quality of results over time.

Within the field of behavior-based robotics, a useful and popular technique for robot control is that of utilitarian voting, where behaviors representing objectives assign utilities to candidate actions. Utilitarian voting allows for distributed, modular control but is not well suited to systems with very high resolution or several, dependent degrees of freedom. Past systems have depended on exhaustive searches that choose the action with the highest combined utility. We present, instead, a framework that casts the action search problem as an anytime algorithm. This allows directed searches to be used with time limit constraints. Aspiration-based satisficing additionally helps to reduce CPU usage. In experiments so far, we have decreased CPU usage by UP to 42% while causing result quality to be no more than 6% worse.

We propose a method based on a real-time search for the proper action of an autonomous mobile robot using the framework of the Anytime Algorithm. This is available for a real-time search in a dynamic environment. In order to apply the Anytime Algorithm to the multi-objective real-time search in the dynamic situation around the autonomous mobile robot, we adopt prediction, a switching evaluation function technique, the action watch dog and an evolution strategy. These enable the robots to realize the real time search. The paper explains the proposed method and shows the feasibility through experimental results using real robots.

We propose an anytime algorithm to compute successively better approximations of the optimum of Minimum Vertex Guard. Though the presentation is focused on polygons, the work may be directly extended to terrains along the lines of [4]. A major idea in our approach is to explore dominance of visibility regions to first detect pieces that are more difficult to guard.

Real-time environments require that decisions be made in time-constrained situations. Traditional deliberation methods which are performed regardless of time considerations are not adequate to meet the demand of this type of environment. Anytime algorithms provide a method for modeling the explicit control of real-time computations. This paper discusses the incorporation of an anytime algorithm to simulation model measures of effectiveness (MOEs). The simulation model was used by an expert system to optimize the selection of an automated guided vehicle (AGV) strategy employed in a manufacturing environment. The problems encountered during the incorporation of an anytime algorithm to the decision-making process are presented, along with the solutions which were developed. >

This paper is motivated to give a recursion-theoretic framework to investigate sequences of knowledge bases such as sequence of iterated revisions and sequence of provisional outputs generated by a so-called anytime algorithm. The global properties of sequence of general knowledge bases are studied by using some concepts such as convergence and logical convergence, which can be considered not only as rationality postulates sequence of iterated revisions but also as basic criteria of adequacy for anytime algorithms for evaluating knowledge bases. A quite surprising result in this paper is that, even in the full first-order logic case, revising a knowledge could be effectively done by an anytime algorithm that produces quickly a first version of the revision and refines it step by step, and these versions approach the revision in limit. It is also investigated that the problem of how to approximately compute an extension in default logic.

The capability to reallocate items-e.g. tasks, securities, bandwidth slices, MW hours of electricity, and collectibles-is a key feature in automated negotiation. Especially when agents have preferences over combinations of items, this is highly nontrivial. Marginal cost based reallocation leads to an anytime algorithm where every agent's utility increases monotonically over time. Different contract types head toward different locally optimal task allocations, and contracts from a recently introduced comprehensive contract type, OCSM-contracts, head toward the global optimum. Reaching it can take an impractically long time, so it is important to trade off solution quality against negotiation time. To construct negotiation protocols that lead to the best achievable allocations in a bounded amount of time, we compared sequences of four contract types. Original, cluster, swap, and multiagent contracts. The experiments show that it is profitable to use multiple contract types in the sequence: significantly better solutions are reached, and faster, than if only one contract type is used. However, the best sequences only include original and cluster contracts. Swap and multiagent contracts lead to bad local optima quickly. Interestingly, the number of contracts using any given contract type does not always decrease over time: contracts play the role of enabling further contracts.

Comparative studies of sets of control parameter values are commonly performed when tuning an evolutionary algorithm for a class of problem instances. The standard approach is to identify the most useful set of control parameter settings for a domain. In this paper, we propose an alternative anytime algorithm portfolio technique in which computational resources are allocated among multiple sets of control parameter value settings. We show a method of optimizing such portfolios by applying a bootstrap sampling approach to a database of individual algorithm performance on instances from a problem distribution. Experiments with genetic algorithms applied to the traveling salesperson domain show that the portfolio approach can yield better performance on a distribution of problem instances than the standard approach of trying to identify the single best configuration for the problem class.

Many real-world medical applications require timely actions to be taken in time pressured situations. Existing approaches to dynamic decision modeling have provided relatively efficient methods for representing and reasoning, but the process of computing the optimal solution has remained intractable. A major reason for this difficulty is the lack of models that are capable of modeling temporal processes and dealing with time-critical situations. This paper presents a formalism called the time-critical dynamic influence diagram that provide the capability for both temporal and space abstraction. To deal with the time criticality, we exploit the concept of space and temporal abstraction to reduce the computational complexity and propose an anytime algorithm for the solution process. We illustrate through out the paper, the various approaches with the use of a medical problem on the treatment of cardiac arrest.

Mediation is presented as an algorithm to be used by a group of agents involved in a negotiation in which relevant information is vast and decentralized. It is an anytime algorithm that enables agents to incrementally reveal information in search of an optimal outcome. Allocation Improvement applies Mediation to the task allocation problem. Its performance is demonstrated on a negotiation problem involving multi-agent planning for intruder tracking.

Thanks to the advances in graphical hardware in the last years, virtual worlds are becoming increasingly popular. Moreover, there exist now standard formats for describing 3D scenes on the web and there is a number of development tools available such as, in the computer games community, editors to design new maps and agent behaviors for popular 3D action games such Unreal, Half-life, or Quake, not to mention general SDKs such as Discreet’s Gmax or Intrinsic’s Alchemy. Nevertheless, it is difficult to “populate” such worlds with virtual agents representing life-like creatures which could autonomously navigate and react to their changing environment, and also possibly interact with users. Pathplanning problems are thus a key issue in the so-called “Game AI” domain [4], and have been tackled up to now with traditional AI techniques such as the classical A* algorithm or more modern extensions, heavily relying on the complete knowledge of the complete virtual environment to define an optimal trajectory for computer-controlled characters. Such classical path-finding is however usually limited to a single goal point and basically amount to compute an optimal or near-optimal trajectory avoiding collision with known obstacles. We will see however that pathfinding can be rephrased as an optimization problem and that constraint-based techniques can be applied to give a reactive anytime algorithm that produce life-like, if not optimal, behaviors for virtual creatures [1]. For the constraint solving aspects, we use a method called Adaptive Search which is based on local search techniques applied to CSPs, inspired by methods such as GSAT and Tabu Search [2]. We are also interested in this work in more complex path-planning, where several goals have to be satisfied by the autonomous agent, which has thus to pass through several destination points in the virtual environment, and we call this problem multi-goal path-finding. This problem appears in a virtual environment or 3D game when, for instance, the user ask some helper agent to go and pick several items and to meet him at some further point. This could also be the case for an autonomous creature who has to “survive” in an unknown environment and for instance look for food but also for water, and so on so forth. In this case also considering multi-goal path-planning as an optimization problem (an instance of the well-known Traveling Salesman Problem) amounts to design new algorithms based on local search techniques, which are also reactive and exhibit opportunistic behaviors for artificial creatures [3].

This paper presents a new approximation methodfor computing arguments or explanations in the context of logic-based argumentative or abductive reasoning. The algorithm can be interrupted at any time returning the solution foundso far. The quality of the approximation increases monotonically when more computational resources are available. The methodis basedon cost functions andreturns lower and upper bounds.

Finding optimal policies for general partially observable Markov decision processes (POMDPs) is computationally difficult primarily due to the need to perform dynamic-programming (DP) updates over the entire belief space. In this paper, we first study a somewhat restrictive class of special POMDPs called almost discernible POMDPs and propose an anytime algorithm called space-progressive value iteration(SPVI). SPVI does not perform DP updates over the entire belief space. Rather it restricts DP updates to a belief subspace that grows over time. It is argued that given sufficient time SPVI can find near-optimal policies for almostdiscernible POMDPs.We then show how SPVI can be applied to more a general class of POMDPs. Empirical results are presented to show the effectiveness of SPVI.

Feature selection is used to improve performance of learning algorithms by finding a minimal subset of relevant features. Since the process of feature selection is computationally intensive, a trade-off between the quality of the selected subset and the computation time is required. In this paper, we are presenting a novel, anytime algorithm for feature selection, which gradually improves the quality of results by increasing the computation time. The algorithm is interruptible, i.e., it can be stopped at any time and provide a partial subset of selected features. The quality of results is monitored by a new measure: fuzzy information gain. The algorithm performance is evaluated on several benchmark datasets.

This paper presents a retrieval method for real-time spatial data browsing through a computer network. This method is designed based on "anytime algorithm" that improves a quality of the processing results over time. The retrieval method decomposes a region specified in a query into sub-regions and searches at each decomposed region using a spatial index. The searched data are kept as the intermediate results for the query and these results are incrementally sent to a client. Consequently, the client can incrementally browse spatial data for the query. We implemented this retrieval system using Java language and constructed a map browsing system as a sample application. Through some experiments, we discussed the effectiveness of our retrieval system.

This paper describes a novel anytime branch-andbound threading search algorithm for gapped block protein sequence-structure alignment with general sequence residue pair interactions. The new algorithm (1) returns a good approximate answer quickly, (2) iteratively improves that answer to the global optimum if allowed more time, (3) eventually produces a proof that the final answer found is indeed the global optimum, and (4) always terminates correctly within a bounded number of steps if allowed sufficient space and time. Using previously published data sets and the Bryant-Lawrence (1993) objective function, the algorithm found the true (proven) global optimum in less than five minutes in alI search spaces size 1O25 or smaller (sequences to 478 residues), and a putative (not guaranteed) optimum in less than five hours in all search spaces size 10” or smaller (sequences to 793 residues, cores to 42 secondary structure segments). If the threading in the largest case were eventually proven to be globally optimal, then the corresponding search speed in the largest case studied would be the equivalent of 1.5 x 1O56 threadings per second, a speed-up exceeding 1O25 over previously published batch branch-and-bound speeds, and exceeding 1050 over previously published exhaustive search speeds, using the same objective function and threading paradigm. Implementation independent measures of search efficiency are defined for equivalent branching factor, depth, and probability of success per draw; empirical data on these measures is given. The general approach should apply to other alignment methodologies and search methods that use a divide-and-conquer strategy.

In this paper, we present a multi-agent system for planning and plan execution monitoring in a real-time railroad transportation scenario. The planning process is implemented as incremental anytime algorithm that is capable of integrating new task specifications in the ongoing planning and plan execution process. An initial solution is obtained by executing the contract-net protocol for every new task, the resulting solution is then optimized by a simulated trading approach. The execution of the resulting plans is monitored by a plan execution monitor that dynamically controls ongoing driving or coupling activities of transportation units and that handles deviations from the original plan in the case of external events, e.g. location route failures or train delays.

We present an approach to the bid-evaluation problem in a system for multi-agent contract negotiation, called MAGNET. The MAGNET market infrastructure provides support for a variety of types of transactions, from simple buying and selling of goods and services to complex multi-agent contract negotiations. In the latter case, MAGNET is designed to negotiate contracts based on temporal and precedence constraints, and includes facilities for dealing with time-based contingencies. One responsibility of a customer agent in the MAGNET system is to select an optimal bid combination. We present an efficient anytime algorithm for a customer agent to select bids submitted by supplier agents in response to a call for bids. Bids might include combinations of subtasks and might include discounts for combinations. In an experimental study we explore the behavior of the algorithm based on the interactions of factors such as bid prices, number of bids, and number of subtasks. The results of experiments we present show that the algorithm is extremely efficient even for large number of bids.

Automated negotiation and coalition formation among self-interested agents are playing an increasingly important role in electronic commerce. Such agents cannot be coordinated by externally imposing their strategies. Instead the interaction protocols have to be designed so that each agent really is motivated to follow the strategies that the protocol designer wants it to follow. The paper reviews six component technologies that have developed for making such interactions less manipulable and more efficient in terms of the computational processes and the outcomes: 1. OCSM-contracts in marginal cost based contracting; 2. Leveled commitment contracts; 3. Anytime coalition structure generation with worst case guarantees; 4. Trading off computation cost against optimization quality within each coalition; 5. Distributing search among insincere agents; and 6. Unenforced contract execution. Each of these technologies represents a different way of battling self-interest and combinatorial complexity simultaneously. This is a key battle when multi-agent systems move into large scale open settings.

We describe a general model of agent action, and ways of constraining action using norms. The agents under study are supersoft agents: autonomous artificial agents programmed to collect, formalise, and actively use qualitative data. A consistent, interruptible, and pre-emptive anytime algorithm that also has measurable quality and diminishing returns is discussed. The algorithm controls procedures for decision making already implemented. The model thus has computational meaning and strives to characterise real-time decision making in agents acting under uncertainty in imprecise and partially described environments.

This paper describes the student modeling component of ANDES, an Intelligent Tutoring System for Newtonian physics. ANDES' student model uses a Bayesian network to do long-term knowledge assessment, plan recognition and prediction of students' actions during problem solving. The network is updated in real time, using an approximate anytime algorithm based on stochastic sampling, as a student solves problems with ANDES. The information in the student model is used by ANDES' Help system to tailor its support when the student reaches impasses in the problem solving process. In this paper, we describe the knowledge structures represented in the student model and discuss the implementation of the Bayesian network assessor. We also present a preliminary evaluation of the time performance of stochastic sampling algorithms to update the network.