Velocity-Based Heuristic Evaluation for Path Planning and Vehicle Routing for Victim Assistance in Disaster Scenarios

摘要

Natural and human-made disasters require effective victim assistance and last-mile relief supply operations with teams of ground vehicles. In these applications, digital elevation models (DEM) can provide accurate knowledge for safe vehicle motion planning but grid representation results in very large search graphs. Furthermore, travel time, which becomes a crucial cost optimization criterion, may be affected by inclination and other challenging terrain characteristics. In this paper, our goal is to evaluate a search heuristic function based on anisotropic vehicle velocity restrictions for building the cost matrix required for multi-vehicle routing on natural terrain and disaster sites. The heuristic is applied to compute the fastest travel times between every pair of matrix elements by means of a path planning algorithm. The analysis is based on a case study on the ortophotographic DEM of natural terrain with different target points, where the proposed heuristic is compared against an exhaustive search solution.