An Approximation Approach for Solving the Subpath Planning Problem
The subpath planning problem is a branch of the path planning problem, which has widespread applications in automated manufacturing process as well as vehicle and robot navigation. This problem is to find the shortest path or tour subject for travelling a set of given subpaths. The current approaches for dealing with the subpath planning problem are all based on meta-heuristic approaches. It is well-known that meta-heuristic based approaches have several deficiencies. To address them, we propose a novel approximation algorithm in the O(n^3) time complexity class, which guarantees to solve any subpath planning problem instance with the fixed ratio bound of 2. Also, the formal proofs of the claims, our empirical evaluation shows that our approximation method acts much better than a state-of-the-art method, both in result and execution time.
Code (0)
등록된 구현이 없습니다.
Tasks
Robot NavigationSimilar Papers 제목 키워드 기반
CARSS: Cooperative Attention-guided Reinforcement Subpath Synthesis for Solving Traveling Salesman Problem
This paper introduces CARSS (Cooperative Attention-guided Reinforcement Subpath Synthesis), a novel approach to address the Traveling Salesman Problem (TSP) by leveraging cooperative Multi-Agent Reinforcement Learning (M…
GPUMulti-agent Reinforcement LearningTraveling Salesman ProblemApproximation Algorithms for ROUND-UFP and ROUND-SAP
We study ROUND-UFP and ROUND-SAP, two generalizations of the classical BIN PACKING problem that correspond to the unsplittable flow problem on a path (UFP) and the storage allocation problem (SAP), respectively. We are g…
Rank-One Modified Value Iteration
In this paper, we provide a novel algorithm for solving planning and learning problems of Markov decision processes. The proposed algorithm follows a policy iteration-type update by using a rank-one approximation of the …
Q-LearningProgressive Smoothing for Motion Planning in Real-Time NMPC
Nonlinear model predictive control (NMPC) is a popular strategy for solving motion planning problems, including obstacle avoidance constraints, in autonomous driving applications. Non-smooth obstacle shapes, such as rect…
Autonomous DrivingModel Predictive ControlMotion PlanningVariational Planning for Graph-based MDPs
Markov Decision Processes (MDPs) are extremely useful for modeling and solving sequential decision making problems. Graph-based MDPs provide a compact representation for MDPs with large numbers of random variables. Howev…
Decision MakingSequential Decision Making