Monte-Carlo Tree Search (MCTS) algorithms estimate the value of MDP states based on rewards received by performing multiple random simulations. MCTS algorithms can use different strategies to aggregate these rewards and provide an estimation for the states’ values. The most common aggregation method is to store the mean reward of all simulations. Another common approach stores the best observed reward from each state. Both of these methods have complementary benefits and drawbacks. In this paper, we show that both of these methods are biased estimators for the real expected value of MDP states. We propose an hybrid approach that uses the best reward for states with low noise, and otherwise uses the mean. Experimental results on the Sailing MDP domain show that our method has a considerable advantage when the rewards are drawn from a noisy distribution.

In the Multi-Agent Path Finding problem (MAPF), we are given a map and a set of agents with distinct source and goal locations. The task is to compute a path for each agent from its initial location to its goal location without conflicting with other agents. MAPF solvers can be divided into classes based on their purpose. One of these classes is the class of online MAPF algorithms, in which the search for paths is interleaved with the actual physical moves of the agents. A prominent algorithm in this class is the Windowed Hierarchical Cooperative A∗ algorithm (WHCA∗) where paths are planned for each agent individually and cooperation is obtained using a reservation table. A number of extensions for WHCA∗ already exist. In this paper we propose a general approach for the baseline WHCA∗ algorithm which is orthogonal to all other existing extensions. We improve WHCA∗ by introducing the Conflict Oriented (CO) principle for focusing the agent coordination around conflicts. In addition, we provide a conflict-oriented prioritization mechanism that intelligently chooses which agent should act next. Experimental results demonstrate the advantage of our approach over WHCA∗.

In this paper we introduce the Target Oriented Network Intelligence Collection (TONIC) problem, which is the problem of finding profiles in a social network that contain information about a given target via automated crawling. We formalize TONIC as a search problem and a best-first approach is proposed for solving it.Several heuristics are presented to guide this search.These heuristics are based on the topology of the currently known part of the social network.The efficiency of the proposed heuristics and the effect of the graph topology on their performance is experimentally evaluated on the Google+ social network.

Multi-agent pathfinding (MAPF) deals with planning paths for individual agents such that a global cost function (e.g., the sum of costs) is minimized while avoiding collisions between agents. Previous work proposed centralized or fully cooperative decentralized algorithms assuming that agents will follow paths assigned to them. When agents are {\em self-interested}, however, they are expected to follow a path only if they consider that path to be their most beneficial option. In this paper we propose the use of a taxation scheme to implicitly coordinate self-interested agents in MAPF. We propose several taxation schemes and compare them experimentally. We show that intelligent taxation schemes can result in a lower total cost than the non coordinated scheme even if we take into consideration both travel cost and the taxes paid by agents.

In the Canadian Traveler Problem (CTP) a traveling agent is given a weighted graph, where some of the edges may be blocked, with a known probability. The agent needs to travel to a given goal. A solution for CTP is a policy, that has the smallest expected traversal cost. CTP is intractable. Previous work has focused on the case of a single agent. We generalize CTP to a repeated task version where a number of agents need to travel to the same goal, minimizing their combined travel cost. We provide optimal algorithms for the special case of disjoint path graphs. Based on a previous UCT-based approach for the single agent case, a framework is developed for the multi-agent case and four variants are given - two of which are based on the results for disjoint-path graphs. Empirical results show the benefits of the suggested framework and the resulting heuristics. For small graphs where we could compare to optimal policies, our approach achieves near optimal results at only a fraction of the computation cost.