  In this article, we consider a multi-agent path planning problem in a
partially impeded environment. The impeded environment is represented by a
graph with select road segments (edges) in disrepair impeding vehicular
movement in the road network. A convoy wishes to travel from a starting
location to a destination while minimizing some accumulated cost. The convoy
may traverse an impeded edge for an additional cost (associated with repairing
the edge) than if it were unimpeded. A second vehicle, referred to as a service
vehicle, is simultaneously deployed with the convoy. The service vehicle
assists the convoy by repairing an edge, reducing the cost for the convoy to
traverse that edge. The convoy is permitted to wait at any vertex to allow the
service vehicle to complete repairing an edge. The service vehicle is permitted
to terminate its path at any vertex. The goal is then to find a pair of paths
so the convoy reaches its destination while minimizing the total time (cost)
the two vehicles are active, including any time the convoy waits. We refer to
this problem as the Assisted Shortest Path Problem (ASPP). We present a
generalized permanent labeling algorithm to find an optimal solution for the
ASPP. We also introduce additional modifications to the labeling algorithm to
significantly improve the computation time and refer to the modified labeling
algorithm as $GPLA^*$. Computational results are presented to illustrate the
effectiveness of $GPLA^*$ in solving the ASPP. We then give concluding remarks
and briefly discuss potential variants of the ASPP for future work.
