15645118
Functional Value Iteration for Decision-Theoretic Planning with General Utility Functions
We study how to find plans that maximize the expected total utility for a given MDP, a planning objective that is important for decision making in high-stakes domains. The optimal actions can now depend on the total reward that has been accumulated so far in addition to the current state. We extend our previous work on functional value iteration from one-switch utility functions to all utility functions that can be approximated with piecewise linear utility functions (with and without exponential tails) by using functional value iteration to find a plan that maximizes the expected total utility for the approximate utility function. Functional value iteration does not maintain a value for every state but a value function that maps the total reward that has been accumulated so far into a value. We describe how functional value iteration represents these value functions in finite form, how it performs dynamic programming by manipulating these representations and what kinds of approximation guarantees it is able to make. We also apply it to a probabilistic blocksworld problem, a standard test domain for decision-theoretic planners.
10288903
Sensor Planning with Non-linear Utility Functions
Sensor planning is concerned with when to sense and what to sense. We study sensor planning in the context of planning objectives that trade-off between minimizing the worst-case, expected, and best-case plan- execution costs. Sensor planning with these planning objectives is interesting because they are realistic and the frequency of sensing changes with the planning objective: more pessimistic decision makers tend to sense more frequently. We perform sensor planning by combining one of our techniques for planning with non-linear utility functions with an existing sensor-planning method. The resulting sensor-planning method is not only as easy to implement as the sensor-planning method that it extends but also (almost) as efficient. We demonstrate empirically how sensor plans change as the planning objective changes, using a common testbed for sensor planning.
3542397
Terrain coverage with ant robots: a simulation study
In this paper, we study a simple means for coordinating teams of simple agents. In particular, we study ant robots and how they can cover terrain once or repeatedly by leaving markings in the terrain, similar to what ants do. These markings can be sensed by all robots and allow them to cover terrain even if they do not communicate with each other except via the markings, do not have any kind of memory, do not know the terrain, cannot maintain maps of the terrain, nor plan complete paths. The robots do not even need to be localized, which completely eliminates solving difficult and time-consuming localization problems. In this paper, we use real-time heuristic search methods to implement ant robots and present a simulation study with several real-time heuristic search methods to study their properties for terrain coverage. Our experiments show that all of the real-time heuristic search methods robustly cover terrain even if the robots are moved without realizing this, some robots fail, and some markings get destroyed. These results demonstrate that terrain coverage with real-time heuristic search methods is an interesting alternative to more conventional terrain coverage methods.
15650619
Value-Function-Based Transfer for Reinforcement Learning Using Structure Mapping
Transfer learning concerns applying knowledge learned in one task (the source) to improve learning another related task (the target). In this paper, we use structure mapping, a psychological and computational theory about analogy making, to find mappings between the source and target tasks and thus construct the transfer functional automatically. Our structure mapping algorithm is a specialized and optimized version of the structure mapping engine and uses heuristic search to find the best maximal mapping. The algorithm takes as input the source and target task specifications represented as qualitative dynamic Bayes networks, which do not need probability information. We apply this method to the Keepaway task from RoboCup simulated soccer and compare the result from automated transfer to that from handcoded transfer.
1322941
Representations of Decision-Theoretic Planning Tasks
Goal-directed Markov Decision Process models (GDMDPs) are good models for many decision-theoretic planning tasks. They have been used in conjunction with two different reward structures, namely the goal-reward representation and the action-penalty representation. We apply GDMDPs to planning tasks in the presence of traps such as steep slopes for outdoor robots or staircases for indoor robots, and study the differences between the two reward structures. In these situations, achieving the goal is often the primary objective while minimizing the travel time is only of secondary importance. We show that the action-penalty representation without discounting guarantees that the optimal plan achieves the goal for sure (if this is possible) but neither the action-penalty representation with discounting nor the goal-reward representation with discounting have this property. We then show exactly when this trapping phenomenon occurs, using a novel interpretation for discounting, namely that it models agents that use convex exponential utility functions and thus are optimistic in the face of uncertainty. Finally, we show how the trapping phenomenon can be eliminated with our Selective State-Deletion Method.
7225251
Keepaway Soccer: From Machine Learning Testbed to Benchmark
Keepaway soccer has been previously put forth as a testbed for machine learning. Although multiple researchers have used it successfully for machine learning experiments, doing so has required a good deal of domain expertise. This paper introduces a set of programs, tools, and resources designed to make the domain easily usable for experimentation without any prior knowledge of RoboCup or the Soccer Server. In addition, we report on new experiments in the Keepaway domain, along with performance results designed to be directly comparable with future experimental results. Combined, the new infrastructure and our concrete demonstration of its use in comparative experiments elevate the domain to a machine learning benchmark, suitable for use by researchers across the field.
15319550
Log-Linear Models for Word Alignment
We present a framework for word alignment based on log-linear models. All knowledge sources are treated as feature functions, which depend on the source language sentence, the target language sentence and possible additional variables. Log-linear models allow statistical alignment models to be easily extended by incorporating syntactic information. In this paper, we use IBM Model 3 alignment probabilities, POS correspondence, and bilingual dictionary coverage as features. Our experiments show that log-linear models significantly outperform IBM translation models.
6564204
A robust method for shape-based 3D model retrieval
Proliferation of 3D models necessitates developing efficient methods for indexing or retrieving the models in a large database. Many previous methods for this purpose defined functions on concentric spheres as approximation of 3D geometry for spherical harmonic transform (SHT). In this paper, we point out that this is not robust as the surface of a model may shift between different shells under perturbation, and multi-layer of surfaces may exist in one shell, making the function definition ambiguous. To solve these problems, we propose a method to characterize 3D shape using delta functions. Then, spherical functions are defined by sampling in the frequency domain of the delta functions for SHT. By doing so, our method can support retrieval with controllable acuity, which benefits wider range of applications and facilitates customization to different users. Experiments have shown that our method is more robust than previous approaches.
6127426
A Complete Axiomatization for Blocks World
Blocks World (BW) has been one of the most popular model domains in AI history. However, there has not been serious work on axiomatizing the state constraints of BW and giving justification for its soundness and completeness. In this paper, we model a state of BW by a finite collection of finite chains, and call the theory of all these structures BW theory. We present seven simple axioms and prove that their consequences are precisely BW theory, using Ehrenfeucht-Fräıssé games. We give a simple decision procedure for the theory which can be implemented in exponential space, and prove that every decision procedure (even if nondeterministic) for the theory must take at least exponential time. We also give a characterization of all nonstandard models for the theory. Finally, we present an expansion of BW theory and show that it admits elimination of quantifiers. As a result, we are able to characterize all definable predicates in BW theory, and give simple examples of undefinable predicates.
36565236
Dynamic Programming via Static Incrementalization
Dynamic programming is an important algorithm design technique. It is used for problems whose solutions involve recursively solving subproblems that share subsubproblems. While a straightforward recursive program solves common subsubproblems repeatedly, a dynamic programming algorithm solves every subsubproblem just once, saves the result, and reuses it when the subsubproblem is encountered again. This can reduce the time complexity from exponential to polynomial. This paper describes a systematic method for transforming programs written as straightforward recursions into programs that use dynamic programming. The method extends the original program to cache all possibly computed values, incrementalizes the extended program with respect to an input increment to use and maintain all cached results, prunes out cached results that are not used in the incremental computation, and uses the resulting incremental program to form an optimized new program. Incrementalization statically exploits semantics of both control structures and data structures and maintains as invariants equalities characterizing cached results. It provides the basis of a general method for achieving drastic program speedups. Compared with previous methods that perform memoization or tabulation, the method based on incrementalization is more powerful and systematic. It has been implemented in a prototype system CACHET and applied to numerous problems and succeeded on all of them.
2949829
On the design of MIMO block-fading channels with feedback-link capacity constraint
In this paper, we propose a combined adaptive power control and beamforming framework for optimizing multiple-input/multiple-output (MIMO) link capacity in the presence of feedback-link capacity constraint. The feedback channel is used to carry channel state information only. It is assumed to be noiseless and causal with a feedback capacity constraint in terms of maximum number of feedback bits per fading block. We show that the hybrid design could achieve the optimal MIMO link capacity, and we derive a computationally efficient algorithm to search for the optimal design under a specific average power constraint. Finally, we shall illustrate that a minimum mean-square error spatial processor with a successive interference canceller at the receiver could be used to realize the optimal capacity. We found that feedback effectively enhances the forward channel capacity for all signal-to-noise ratio (SNR) values when the number of transmit antennas (n/sub T/) is larger than the number of receive antennas (n/sub R/). The SNR gain with feedback is contributed by focusing transmission power on active eigenchannel and temporal power waterfilling . The former factor contributed, at most, 10log/sub 10/(n/sub T//n/sub R/) dB SNR gain when n/sub T/>n/sub R/, while the latter factor's SNR gain is significant only for low SNR values.