Agents that solve problems in unknown graphs are usually required to iteratively explore parts of the graph. In this paper we research the problem of finding a k-clique in an unknown graph while minimizing the number of required exploration actions. Two novel heuristics Known Degree and Clique* are proposed to reduce the required exploration cost by carefully choosing which part of the environment to explore. We further investigate the problem by adding probabilistic knowledge of the graph and propose an Markov Decision Process(MDP) and a Monte Carlo based heuristic (RClique*) that uses knowledge of edge probabilities to reduce the required exploration cost. We demonstrate the efficiency of the proposed approaches on simulated random and scale free graphs as well as on real online web crawls.

HDA* is a simple, parallelization of A* where work is asynchronously distributed among the nodes by a global hash function. Using up to 1024 cores on a large distributed memory cluster, we evaluate HDA* for a domain-independent planner as well an application-specific 24-puzzle solver. We show that HDA* scales fairly well on a large cluster using up to 1024 cores. Our analysis of the scaling behavior shows that on a cluster of multicore nodes, using only a subset of the available cores and leaving some cores idle can, surprisingly, lead to better results.

True distance memory-based heuristics (TDHs) were recently introduced as a way to obtain admissible heuristics for explicit state spaces. In this paper, we introduce a new TDH, the portal-based heuristic. The domain is partitioned into regions and portals between regions are identified. True distances between all pairs of portals are stored and used to obtain admissible heuristics throughout the search. We introduce an A*-based algorithm that takes advantage of the special properties of the new heuristic. We study the advantages and limitations of the new heuristic. Our experimental results show large performance improvements over previously-reported TDHs for commonly used classes of maps.

Transposition tables are a well-known method for pruning duplicates in heuristic search. This paper presents a detailed analysis of transposition tables for IDA*. We show that some straightforward implementations of IDA* with transposition tables (IDA*+TT) can result in suboptimal solutions being returned. Furthermore, straightforward implementations of IDA*+TT are not complete. We identify several variants of IDA*+TT which are guaranteed to return the optimal solution, as well as a complete variant. An empirical study shows that IDA*+TT can significantly improve upon the performance of A* in domain-independent planning.

Support vector machines (SVMs) are invaluable tools for many practical applications in artificial intelligence, e.g., classification and event recognition. However, popular SVM solvers are not sufficiently efficient for applications with a great deal of samples as well as a large number of features. In this paper, thus, we present NESVM, a fast gradient SVM solver that can optimize various SVM models, e.g., classical SVM, linear programming SVM and least square SVM. Compared against SVM-Perf \cite{SVM_Perf}\cite{PerfML} (its convergence rate in solving the dual SVM is upper bounded by $\mathcal O(1/\sqrt{k})$, wherein $k$ is the number of iterations.) and Pegasos \cite{Pegasos} (online SVM that converges at rate $\mathcal O(1/k)$ for the primal SVM), NESVM achieves the optimal convergence rate at $\mathcal O(1/k^{2})$ and a linear time complexity. In particular, NESVM smoothes the non-differentiable hinge loss and $\ell_1$-norm in the primal SVM. Then the optimal gradient method without any line search is adopted to solve the optimization. In each iteration round, the current gradient and historical gradients are combined to determine the descent direction, while the Lipschitz constant determines the step size. Only two matrix-vector multiplications are required in each iteration round. Therefore, NESVM is more efficient than existing SVM solvers. In addition, NESVM is available for both linear and nonlinear kernels. We also propose "homotopy NESVM" to accelerate NESVM by dynamically decreasing the smooth parameter and using the continuation method. Our experiments on census income categorization, indoor/outdoor scene classification, event recognition and scene recognition suggest the efficiency and the effectiveness of NESVM. The MATLAB code of NESVM will be available on our website for further assessment.

We provide a series of algorithms demonstrating that solutions according to the fundamental game-theoretic solution concept of closed under rational behavior (CURB) sets in two-player, normal-form games can be computed in polynomial time (we also discuss extensions to n-player games). First, we describe an algorithm that identifies all of a players best responses conditioned on the belief that the other player will play from within a given subset of its strategy space. This algorithm serves as a subroutine in a series of polynomial-time algorithms for finding all minimal CURB sets, one minimal CURB set, and the smallest minimal CURB set in a game. We then show that the complexity of finding a Nash equilibrium can be exponential only in the size of a games smallest CURB set. Related to this, we show that the smallest CURB set can be an arbitrarily small portion of the game, but it can also be arbitrarily larger than the supports of its only enclosed Nash equilibrium. We test our algorithms empirically and find that most commonly studied academic games tend to have either very large or very small minimal CURB sets.

Addressing the problem of spam emails in the Internet, this paper presents a comparative study on Na\"ive Bayes and Artificial Neural Networks (ANN) based modeling of spammer behavior. Keyword-based spam email filtering techniques fall short to model spammer behavior as the spammer constantly changes tactics to circumvent these filters. The evasive tactics that the spammer uses are themselves patterns that can be modeled to combat spam. It has been observed that both Na\"ive Bayes and ANN are best suitable for modeling spammer common patterns. Experimental results demonstrate that both of them achieve a promising detection rate of around 92%, which is considerably an improvement of performance compared to the keyword-based contemporary filtering approaches.

The four intensive problems to the software rose by the software industry .i.e., User System Communication / Human Machine Interface, Meta Data extraction, Information processing & management and Data representation are discussed in this research paper. To contribute in the field we have proposed and described an intelligent semantic oriented agent based search engine including the concepts of intelligent graphical user interface, natural language based information processing, data management and data reconstruction for the final user end information representation.

This paper models a decision support system to predict the occurance of suicide attack in a given collection of cities. The system comprises two parts. First part analyzes and identifies the factors which affect the prediction. Admitting incomplete information and use of linguistic terms by experts, as two characteristic features of this peculiar prediction problem we exploit the Theory of Fuzzy Soft Sets. Hence the Part 2 of the model is an algorithm vz. FSP which takes the assessment of factors given in Part 1 as its input and produces a possibility profile of cities likely to receive the accident. The algorithm is of O(2^n) complexity. It has been illustrated by an example solved in detail. Simulation results for the algorithm have been presented which give insight into the strengths and weaknesses of FSP. Three different decision making measures have been simulated and compared in our discussion.

In many multiagent domains a set of agents exert effort towards a joint outcome, yet the individual effort levels cannot be easily observed. A typical example for such a scenario is routing in communication networks, where the sender can only observe whether the packet reached its destination, but often has no information about the actions of the intermediate routers, which influences the final outcome. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a basic ''combinatorial agency'' model for this setting, where the principal is restricted to inducing a pure Nash equilibrium. Here we study various implications of this restriction. First, we show that, in contrast to the case of observable efforts, inducing a mixed-strategies equilibrium may be beneficial for the principal. Second, we present a sufficient condition for technologies for which no gain can be generated. Third, we bound the principal's gain for various families of technologies. Finally, we study the robustness of mixed equilibria to coalitional deviations and the computational hardness of the optimal mixed equilibria.