Efficient Bi- and Multi-Objective Search Algorithms

Searching larger networks, such as street maps, is a fundamental problem in computer science with numerous applications in fields like robotics, artificial intelligence (AI) and more. In standard search problems, one needs to find the shortest path, e. g., between two locations in a map or there is a single cost function to minimize, e. g. travel time. Indeed, AI has made amazing progress to speeding up searches on large networks over the past years and one can typically compute any path between two locations on a roadmap at an astonishing speed. However, many applications are concerned with two (or more) competing resources, such as traversal time and energy. Examples include solving transportation problems, planning power-transmission lines, scheduling satellites, and routing packets in computer networks. In this case, one needs bi-objective (or multi-objective) search algorithms. Here, we aim to develop paths with low costs for both functions. This is not a simple challenge by any means and we propose advanced techniques to address this problem. Specifically, we propose to combine ideas from existing bi-objective search algorithms with concepts from the AI search community in order to develop the next generation of optimal and approximately-optimal bi-objective search algorithms that will allow for real-time searches on much larger graphs than is currently possible. We then intend to exploit various speed-up techniques used in the AI search community to make bi-objective search algorithms even faster. Many broader impacts include faster bi- and multi-objective search algorithms will enable new applications, for example, by enabling path finding on large road networks in real-time and balancing path length and safety when planning for a robotic system.