Reinforcement Learning Based Monte Carlo Tree Search for Temporal Path Discovery An Attributed Dynamic Graph (ADG) contains multiple dynamic attributes associated with each edge. In ADG based applications, people usually can specify multiple constrains in the attributes to illustrate their requirements, such as the total cost, the total travel time and the stopover interval of a flight between two cities. This inspires a type of MultiConstrained Temporal Path (MCTP) discovery in ADGs, which is a challenging NPComplete problem. In order to deliver an efficient and effective temporal path discovery method to be used in realtime environment, we propose a Reinforcement Learning (RL) based, Monte Carlo Tree Search algorithm (RLMCTS). RLMCTS uses a newly designed memory structure to address the challenges of Monte Carlo Tree Search (MCTS) in MCTP discovery. To the best of our knowledge, RLMCTS is the first RL algorithm that supports path discovery in ADGs. The experimental results on ten real dynamic graphs demonstrate that our algorithm outperforms the stateoftheart methods in terms of both efficiency and effectiveness.

Online Planning for Autonomous Underwater Vehicles Performing Information Gathering Tasks in Large Subsea Environments We present an anytime Monte Carlo tree search (MCTS) algorithm to generate realtime, nearoptimal search paths in large subsea environments. The MCTS planner continuously builds a tree of the search space until either the allowed time per move is reached or the budget constraint for the search mission is met. In order to improve the performance of the MCTS planner, we propose a novel heuristic action selection policy to determine the value of a leaf node. The proposed heuristic is tailored to problems where making a turn incurs a higher cost than moving straight, such as the case on autonomous underwater vehicles. Through extensive simulations, we show that our heuristic yields a significant performance improvement over a lawnmover path planner xe2x80x93 a commonly employed approach in subsea search applications xe2x80x93 and over a simple MCTS planner where actions are selected uniformly at random. In our numerical illustrations, we use a real data set abstracted from sonar measurements acquired from the Boston Harbor.