Using Combined Knapsack and Shortest Path Problems for Planning Optimal Navigation Paths for Robotic Deliveries

Abstract

Today., the use of robotic navigational tools is widely used both in academical research and the technological industry., there is a growing need for planning paths of navigation to autonomous machines., robots and transportation vehicles. In this paper we relate to a specific problem in which the robot has to navigate between several points of delivery., every point contains several items that all have different weights and different values. There are two widely researched problems in computer science algorithms., namely the knapsack problem and the shortest paths on weighted graphs problem. Typically., dynamic programming solutions for the knapsack problem involve using the shortest path problem and creating a knapsack graph. However., this approach only considers the weight and value of each item or vertex. In our case., we introduce a different problem where we consider three properties: item weight., item value., and edge weight (which connects two items but is not dependent on its vertices). Each vertex in this particular graph represents a set of knapsack items. This scenario is applicable to real-life situations where a path has a non-dependent attribute (such as physical distance or travel time) and various types of items need to be selected at different locations along this path. The problem we address here is finding the most efficient path between two vertices (source and target) based on three aspects: minimal edge weight., maximum knapsack value., or a combination of both properties. We present an algorithm for finding these optimal paths., along with detailed explanations of its decision-making process and implementation.