Model minimization in Factored Markov Decision Processes (FMDPs) is concerned with finding the most compact partition of the state space such that all states in the same block are action-equivalent. This is an important problem because it can potentially transform a large FMDP into an equivalent but much smaller one, whose solution can be readily used to solve the original model. Previous model minimization algorithms are iterative in nature, making opaque the relationship between the input model and the output partition. We demonstrate that given a set of well-defined concepts and operations on partitions, we can express the model minimization problem in an analytic fashion. The theoretical results developed can be readily applied to solving problems such as estimating the size of the minimum partition, refining existing algorithms, and so on.

A moving k-nearest-neighbor (MKNN) query is a continuous k-nearest-neighbor (KNN) query issued by a moving object. As both the query owner and other mobile objects are moving, the influenced area (i.e., cells in the cellular networks), and query result of a MKNN query change with time. Existing processing techniques for MKNN queries are all centralized approaches which rely on the location update messages from moving objects. However, these approaches typically employ complex data structures and algorithms. Moreover, the server may not be able to cope with a high location report rate which is necessary to ensure accurate and correct answers. In this paper, we propose a distributed strategy to process MKNN queries in real-time. In our scheme, called disMKNN, the server and moving objects collaborate to maintain the KNN of a MKNN query. While the server keeps track of a MKNN query's influenced cells, moving objects within the cells monitor their own relationships (i.e., whether they are part of the KNN answers) to the query. Results of an extensive performance study show the effectiveness of disMKNN.