Simple board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in the development of mathematical and logical skills, but also in the emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. We present an approach that generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. The presence of such states for standard game variants like 4 x 4 Tic-Tac-Toe opens up new games to be played that have never been played as the default start state is heavily biased.

This paper presents a novel approach to inductive process modeling, the task of constructing a quantitative account of dynamical behavior from time-series data and background knowledge. We review earlier work on this topic, noting its reliance on methods that evaluate entire model structures and use repeated simulation to estimate parameters, which together make severe computational demands. In response, we present an alternative method for process model induction that assumes each process has a rate, that this rate is determined by an algebraic expression, and that changes due to a process are directly proportionalto its rate. We describe RPM, an implemented system that incorporates these ideas, and we report analyses and experiments that suggest it scales well to complex domains and data sets. In closing, we discuss related research and outline ways to extend the framework.

Point-of-interest(POI) recommendation becomes a valuable service in location-based social networks. Based on the norm that similar users are likely to have similar preference of POIs, the current recommendation techniques mainly focus on users' preference to provide accurate recommendation results. This tends to generate a list of homogeneous POIs that are clustered into a narrow band of location categories(like food, museum, etc.) in a city. However, users are more interested to taste a wide range of flavors that are exposed in a global set of location categories in the city.In this paper, we formulate a new POI recommendation problem, namely top-K location category based POI recommendation, by introducing information coverage to encode the location categories of POIs in a city.The problem is NP-hard. We develop a greedy algorithm and further optimization to solve this challenging problem. The experimental results on two real-world datasets demonstrate the utility of new POI recommendations and the superior performance of the proposed algorithms.

Attribute reduction is a basic issue in knowledge representation and data mining. Rough sets provide a theoretical foundation for the issue. Matroids generalized from matrices have been widely used in many fields, particularly greedy algorithm design, which plays an important role in attribute reduction. Therefore, it is meaningful to combine matroids with rough sets to solve the optimization problems. In this paper, we introduce an existing algebraic structure called dependence space to study the reduction problem in terms of matroids. First, a dependence space of matroids is constructed. Second, the characterizations for the space such as consistent sets and reducts are studied through matroids. Finally, we investigate matroids by the means of the space and present two expressions for their bases. In a word, this paper provides new approaches to study attribute reduction.

This paper considers a recently emerged hyperspectral unmixing formulation based on sparse regression of a self-dictionary multiple measurement vector (SD-MMV) model, wherein the measured hyperspectral pixels are used as the dictionary. Operating under the pure pixel assumption, this SD-MMV formalism is special in that it allows simultaneous identification of the endmember spectral signatures and the number of endmembers. Previous SD-MMV studies mainly focus on convex relaxations. In this study, we explore the alternative of greedy pursuit, which generally provides efficient and simple algorithms. In particular, we design a greedy SD-MMV algorithm using simultaneous orthogonal matching pursuit. Intriguingly, the proposed greedy algorithm is shown to be closely related to some existing pure pixel search algorithms, especially, the successive projection algorithm (SPA). Thus, a link between SD-MMV and pure pixel search is revealed. We then perform exact recovery analyses, and prove that the proposed greedy algorithm is robust to noise---including its identification of the (unknown) number of endmembers---under a sufficiently low noise level. The identification performance of the proposed greedy algorithm is demonstrated through both synthetic and real-data experiments.

The Atari 2600 games supported in the Arcade Learning Environment (Bellemare et al. 2013) all feature aknown initial (RAM) state and actions that have deterministic effects. Classical planners, however, cannot be used for selecting actions for two reasons: first, nocompact PDDL-model of the games is given, and more importantly, the action effects and goals are not known a priori. Moreover, in these games there is usually no set of goals to be achieved but rewards to be collected. These features do not preclude the use of classical algorithms like breadth-first search or Dijkstra’s algorithm, but these methods are not effective over large state spaces. We thus turn to a different class of classical planning algorithms introduced recently that perform a structured exploration of the state space; namely, like breadth-first search and Dijkstra’s algorithm they are“blind” and hence do not require prior knowledge of state transitions, costs (rewards) or goals, and yet, like heuristic search algorithms, they have been shown to be effective for solving problems over huge state spaces.The simplest such algorithm, called Iterated Width or IW, consists of a sequence of calls IW(1), IW(2), . . . ,IW(k) where IW(i) is a breadth-first search in which a state is pruned when it is not the first state in the search to make true some subset of i atoms. The empirical results over 54 games suggest that the performance of IW with the k parameter fixed to 1, i.e., IW(1), is at the level of the state of the art represented by UCT. A simple best-first variation of IW that combines exploration and exploitation proves to be very competitive as well.

The paper explores the potential of weighted best-first search schemes as anytime optimization algorithms for solving graphical models tasks such as MPE (Most Probable Explanation) or MAP (Maximum a Posteriori) and WCSP (Weighted Constraint Satisfaction Problem). While such schemes were widely investigated for path-finding tasks, their application for graphical models was largely ignored, possibly due to their memory requirements. Compared to the depth-first branch and bound, which has long been the algorithm of choice for optimization in graphical models, a valuable virtue of weighted best-first search is that they are w-optimal, i.e. when terminated, they return a solution cost C and a weight w, such that C < = wC*, where C* is the optimal cost. We report on a significant empirical evaluation, demonstrating the usefulness of weighted best-first search as approximation anytime schemes (that have suboptimality bounds) and compare against one of the best depth-first branch and bound solver to date. We also investigate the impact of different heuristic functions on the behaviour of the algorithms.

To achieve high performance, autonomous systems, such as science explorers, should adapt to the environment to improve utility gained, as well as robustness. Flexibility during temporal plan execution has been explored extensively to improve robustness, where flexibility exists both in activity choices and schedules. These problems are framed as conditional constraint networks over temporal constraints. However, flexibility has been exploited in a limited form to improve utility. Prior work considers utility in choice or schedule, but not their coupling. To exploit fully flexibility, we introduce conditional simple temporal networks with preference (CSTNP), where preference is a function over both choice and schedule. Enumerating best solutions to a CSTNP is challenging due to the cost of scheduling a candidate STPP and the exponential number of candidates. Our contribution is an algorithm for enumerating solutions to CSTNPs efficiently, called A star with bounding conflicts (A*BC), and a novel variant of conflicts, called bounding conflicts, for learning heuristic functions. A*BC interleaves Generate, Test, and Bound. When A*BC bounds a candidate, by solving a STPP, it generates a bounding conflict, denoting neighboring candidates with similar bounds. A*BC's generator then uses these conflicts to steer away from sub-optimal candidates.

We examine a decomposition approach to find good quality feasible solutions. In particular, we studya method to reduce the search-space by decomposing a problem into two partitions, where the second partition (i.e., the subproblem) contains the fixed solution of the first (i.e., the master). This type of approach is usually motivated by the presence of two sub-problems that are each more easily solved by different methods. Our work is motivated by methods for which it is nontrivial to return a strong `no-good', `Benders feasibility', or 'optimality' cut. Instead, we focus our attention on a uni-directional decomposition approach. Instead of providing a relaxation of the sub-problem for the master problem, as in Benders decomposition, we provide an approximation of the sub-problem. Thus, we aim at finding good quality feasible solutions in the first iteration. While the quality of the approximation itself affects the impact of this approach, we illustrate that even using a simple approximation can havestrong positive impact on two examples: the Travelling Purchaser Problem and a Mine Planning Problem.

Answering point-to-point distance queries is important inmany applications, including games, robotics and vehiclerouting in operations research. Searching in a graph to answer distance queries on demandcan often be too slow.An alternative strategy, taken in methods such asTransit and Hub Labels, is to pre-compute information that can help computedistances much faster.To be practical, such methods need to generate muchless preprocessed data than a naive all-pairs distance table. We present Heuristic-Aid Compressed Distance Databases (HCDs),pre-computed data structures based on the observation thatheuristic distance estimations can sometimes coincide with true distances.Compared to a naive all-pairs distance table,we report compression factors of two to three orders of magnitude in a wide range ofmaps, reducing the memory usage to a reasonable size. Comparedto compressed path databases, our approachgenerally generates smaller databases, and answers query distances faster.