Recent progress in randomized motion planners has led to the development of a\nnew class of sampling-based algorithms that provide asymptotic optimality\nguarantees, notably the RRT* and the PRM* algorithms. Careful analysis reveals\nthat the so-called "rewiring" step in these algorithms can be interpreted as a\nlocal policy iteration (PI) step (i.e., a local policy evaluation step followed\nby a local policy improvement step) so that asymptotically, as the number of\nsamples tend to infinity, both algorithms converge to the optimal path almost\nsurely (with probability 1). Policy iteration, along with value iteration (VI)\nare common methods for solving dynamic programming (DP) problems. Based on this\nobservation, recently, the RRT$^{\\#}$ algorithm has been proposed, which\nperforms, during each iteration, Bellman updates (aka "backups") on those\nvertices of the graph that have the potential of being part of the optimal path\n(i.e., the "promising" vertices). The RRT$^{\\#}$ algorithm thus utilizes\ndynamic programming ideas and implements them incrementally on randomly\ngenerated graphs to obtain high quality solutions. In this work, and based on\nthis key insight, we explore a different class of dynamic programming\nalgorithms for solving shortest-path problems on random graphs generated by\niterative sampling methods. These class of algorithms utilize policy iteration\ninstead of value iteration, and thus are better suited for massive\nparallelization. Contrary to the RRT* algorithm, the policy improvement during\nthe rewiring step is not performed only locally but rather on a set of vertices\nthat are classified as "promising" during the current iteration. This tends to\nspeed-up the whole process. The resulting algorithm, aptly named Policy\nIteration-RRT$^{\\#}$ (PI-RRT$^{\\#}$) is the first of a new class of DP-inspired\nalgorithms for randomized motion planning that utilize PI methods.\n