An official website of the United States government
The safe internal transportation of hazardous materials within healthcare facilities is critical to mitigating risks to patients, staff, and visitors. This paper presents a risk-averse path planning framework for autonomously handling hazardous materials in healthcare systems. We model the indoor environment with grid-based obstacle and risk maps, where risk arises from pedestrian flow density and proximity to critical zones. Our novel risk-averse path planning approach integrates risk directly into each transition cost, thereby enabling more robust and secure path selection. We further improve efficiency through (i) a bidirectional variant that cuts search time and (ii) a post-optimization step that minimizes unnecessary heading changes while respecting a risk budget. We evaluated our framework on multiple simulated grid maps and compared it with established methods, measuring path length, average risk, and computational time. The results demonstrate that the proposed framework consistently generates safe and efficient paths while minimizing computational overhead.
more »
« less
Toward a String-Pulling Approach to Path Smoothing on Grid Graphs
Paths found on grid graphs are often unrealistic looking in the continuous environment that the grid graph represents and often need to be smoothed after a search. The well-known algorithm for path smoothing is greedy in nature and does not necessarily eliminate all heading changes in freespace. We present preliminary research toward a new path-smoothing algorithm based on 'string pulling' and show experimentally that it consistently finds shorter paths than the greedy path-smoothing algorithm and produces paths with no heading changes in freespace.
more »
« less
- Award ID(s):
- 1724392
- PAR ID:
- 10179964
- Date Published:
- Journal Name:
- Symposium on Combinatorial Search (SoCS)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this work, we present a novel method for constructing a topological map of biological hotspots in an aquatic environment using a Fast Marching-based Voronoi segmentation. Using this topological map, we develop a closed form solution to the scheduling problem for any single path through the graph. Searching over the space of all paths allows us to compute a maximally informative path that traverses a subset of the hotspots, given some budget. Using a greedy-coverage algorithm we can then compute an informative path. We evaluate our method in a set of simulated trials, both with randomly generated environments and a real-world environment. In these trials, we show that our method produces a topological graph which more accurately captures features in the environment than standard thresholding techniques. Additionally, We show that our method can improve the performance of a greedy-coverage algorithm in the informative path planning problem by guiding it to different informative areas to help it escape from local maxima.more » « less
-
Due to the recent COVID-19 outbreak, makeshift (MS) hospitals have become an important feature in healthcare systems worldwide. Healthcare personnel (HCP) need to be able to navigate quickly, effectively, and safely to help patients, while still maintaining their own well-being. In this study, a pathfinding algorithm to help HCP navigate through a hospital safely and effectively is developed and verified. Tests are run using a discretized 2D grid as a representation of an MS hospital plan, and total distance traveled and total exposure to disease are measured. The influence of the size of the 2D grid units, the shape of these units, and degrees of freedom in the potential movement of the HCP are investigated. The algorithms developed are designed to be used in MS hospitals where airborne illness is prevalent and could greatly reduce the risk of illness in HCP. In this study, it was found that the quantum-based algorithm would generate paths that accrued 50–66% less total disease quantum than the shortest path algorithm with also about a 33–50% increase in total distance traveled. It was also found that the mixed path algorithm-generated paths accrued 33–50% less quantum, but only increased total distance traveled by 10–20%.more » « less
-
N/A (Ed.)Abstract—The Resource Constrained Shortest Path Problem (RCSPP) seeks to determine a minimum-cost path between a start and a goal location while ensuring that one or multiple types of resource consumed along the path do not exceed their limits. This problem is often solved on a graph where a path is incrementally built from the start towards the goal during the search. RCSPP is computationally challenging as comparing these partial solution paths is based on multiple criteria (i.e., the accumulated cost and resource along the path), and in general, there does not exist a single path that optimizes all criteria simultaneously. Consequently, the search needs to maintain and explore a large number of partial paths in order to find an optimal solution. While a variety of algorithms have been developed to solve RCSPP, they either have little consideration about efficiently comparing and maintaining the partial paths, which reduces their overall runtime efficiency, or are restricted to handle only one resource constraint as opposed to multiple resource constraints. This paper develops Enhanced Resource Constrained A* (ERCA*), a fast A*-based algorithm that can find an optimal solution while satisfying multiple resource constraints. ERCA* leverages both the recent advances in multi-objective path planning to efficiently compare and maintain partial paths, and techniques from the existing RCSPP literature. Furthermore, ERCA* has a functional parameter to broker a trade-off between solution quality and runtime efficiency. The results show ERCA* often runs several orders of magnitude faster than an existing leading algorithm for RCSPP.more » « less
-
In this paper, we propose the greedy smallest-cost-rate path first (GRASP) algorithm to route power from sources to loads in a digital microgrid (DMG). Routing of power from distributed energy resources (DERs) to loads of a DMG comprises matching loads to DERs and the selection of the smallest-cost-rate path from a load to its supplying DERs. In such a microgrid, one DER may supply power to one or many loads, and one or many DERs may supply the power requested by a load. Because the optimal method is NP-hard, GRASP addresses this high complexity by using heuristics to match sources and loads and to select the smallest-cost-rate paths in the DMG. We compare the cost achieved by GRASP and an optimal method based on integer linear programming on different IEEE test feeders and other test networks. The comparison shows the trade-offs between lowering complexity and achieving optimal-cost paths. The results show that the cost incurred by GRASP approaches that of the optimal solution by small margins. In the adopted networks, GRASP trades its lower complexity for up to 18% higher costs than those achieved by the optimal solution.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
