An official website of the United States government
Summary Path planning is a fundamental and critical task in many robotic applications. For energy‐constrained robot platforms, path planning solutions are desired with minimum time arrivals and minimal energy consumption. Uncertain environments, such as wind conditions, pose challenges to the design of effective minimum time‐energy path planning solutions. In this article, we develop a minimum time‐energy path planning solution in continuous state and control input spaces using integral reinforcement learning (IRL). To provide a baseline solution for the performance evaluation of the proposed solution, we first develop a theoretical analysis for the minimum time‐energy path planning problem in a known environment using the Pontryagin's minimum principle. We then provide an online adaptive solution in an unknown environment using IRL. This is done through transforming the minimum time‐energy problem to an approximate minimum time‐energy problem and then developing an IRL‐based optimal control strategy. Convergence of the IRL‐based optimal control strategy is proven. Simulation studies are developed to compare the theoretical analysis and the proposed IRL‐based algorithm.
more »
« less
Integer Programming as a General Solution Methodology for Path-Based Optimization in Robotics: Principles, Best Practices, and Applications
Integer programming (IP) has proven to be highly effective in solving many path-based optimization problems in robotics. However, the applications of IP are generally done in an ad-hoc, problem-specific manner. In this work, after examined a wide range of path-based optimization problems, we describe an IP solution methodology for these problems that is both easy to apply (in two simple steps) and high-performance in terms of the computation time and the achieved optimal- ity. We demonstrate the generality of our approach through the application to three challenging path-based optimization problems: multi-robot path planning (MPP), minimum constraint removal (MCR), and reward collection problems (RCPs). Associ- ated experiments show that the approach can efficiently produce (near-)optimal solutions for problems with large state spaces, complex constraints, and complicated objective functions. In conjunction with the proposition of the IP methodology, we introduce two new and practical robotics problems: multi-robot minimum constraint removal (MMCR) and multi-robot path planning (MPP) with partial solutions, which can be quickly and effectively solved using our proposed IP solution pipeline.
more »
« less
- PAR ID:
- 10111595
- Date Published:
- Journal Name:
- IEEE/RSJ International Conference on Intelligent Robots and Systems
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this preliminary study, we propose a new centralized decoupled algorithm for solving one-shot and dynamic optimal multi-robot path planning problems in a grid- based setting mainly targeting warehouse like environments. In particular, we exploit two novel and effective heuristics: path diversification and optimal sub-problem solution databases. Preliminary evaluation efforts demonstrate that our method achieves promising scalability and good solution optimality.more » « less
-
null (Ed.)Complex service robotics scenarios entail unpredictable task appearance both in space and time. This requires robots to continuously relocate and imposes a trade-off between motion costs and efficiency in task execution. In such scenarios, multi-robot systems and even swarms of robots can be exploited to service different areas in parallel. An efficient deployment needs to continuously determine the best allocation according to the actual service needs, while also taking relocation costs into account when such allocation must be modified. For large scale problems, centrally predicting optimal allocations and movement paths for each robot quickly becomes infeasible. Instead, decentralized solutions are needed that allow the robotic system to self-organize and adaptively respond to the task demands. In this paper, we propose a distributed and asynchronous approach to simultaneous task assignment and path planning for robot swarms, which combines a bio-inspired collective decision-making process for the allocation of robots to areas to be serviced, and a search-based path planning approach for the actual routing of robots towards tasks to be executed. Task allocation exploits a hierarchical representation of the workspace, supporting the robot deployment to the areas that mostly require service. We investigate four realistic environments of increasing complexity, where each task requires a robot to reach a location and work for a specific amount of time. The proposed approach improves over two different baseline algorithms in specific settings with statistical significance, while showing consistently good results overall. Moreover, the proposed solution is robust to limited communication and robot failures.more » « less
-
null (Ed.)Robot motion planning is one of the important elements in robotics. In environments full of obstacles, it is always challenging to find a collision-free and dynamically feasible path between the robot's initial configuration and goal configuration. While many motion planning algorithms have been proposed in the past, each of them has its pros and cons. This work presents a benchmark which implements and compares existing planning algorithms on a variety of problems with extensive simulation. Based on that, we also propose a hybrid planning algorithm, RRT*-CFS, that combines the merits of sampling-based planning methods and optimization-based planning methods. The first layer, RRT*, quickly samples a semi-optimal path. The second layer, CFS, performs sequential convex optimization given the reference path from RRT*. The proposed RRT*-CFS has feasibility and convergence guarantees. Simulation results show that RRT*-CFS benefits from the hybrid structure and performs robustly in various scenarios including the narrow passage problems.more » « less
-
Fast algorithms for optimal multi-robot path planning are sought after in both research and real-world applications. Known methods, however, generally do not simultaneously guarantee good solution optimality and fast run time for difficult instances. In this work, we develop a low-polynomial running time algorithm, called SplitAndGroup, that solves the multi-robot path planning problem on grids and grid-like environments, and produces constant factor time- and distance-optimal solutions, in expectation. In particular, SplitAndGroup computes solutions with sub-linear makespan. SplitAndGroup is capable of handling cases when the density of robot is extremely high - in a graph-theoretic setting, the algorithm supports cases where all vertices of the underlying graph are occupied by robots. SplitAndGroup attains its desirable properties through a careful combination of divide-and-conquer technique and network flow based methods for routing the robots.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
