skip to main content


Title: 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
NSF-PAR ID:
10179964
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Symposium on Combinatorial Search (SoCS)
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We designed an observer-aware method for creating navigation paths that simultaneously indicate a robot’s goal while attempting to remain in view for a particular observer. Prior art in legible motion does not account for the limited field of view of observers, which can lead to wasted communication efforts that are unobserved by the intended audience. Our observer-aware legibility algorithm directly models the locations and perspectives of observers, and places legible movements where they can be easily seen. To explore the effectiveness of this technique, we performed a 300-person online user study. Users viewed first-person videos of restaurant scenes with robot waiters moving along paths optimized for different observer perspectives, along with a baseline path that did not take into account any observer’s field of view. Participants were asked to report their estimate of how likely it was the robot was heading to their table versus the other goal table as it moved along each path. We found that for observers with incomplete views of the restaurant, observer-aware legibility is effective at increasing the period of time for which observers correctly infer the goal of the robot. Non-targeted observers have lower performance on paths created for other observers than themselves, which is the natural drawback of personalizing legible motion to a particular observer. We also find that an observer’s relationship to the environment (e.g. what is in their field of view) has more influence on their inferences than the observer’s relative position to the targeted observer, and discuss how this implies knowledge of the environment is required in order to effectively plan for multiple observers at once. 
    more » « less
  2. This dataset includes multiple fields: (i) files for monthly and annual fields for the max curl line and the zero curl line at 0.1 degree longitudinal resolutions; (ii) files for monthly and annual GS path obtained from Altimetry and originally processed by Andres (2016) at 0.1 degree longitudinal resolution. The maximum curl line (MCL) and the zero curl line (ZCL) calculations are briefly described here and are based on the original wind data (at 1.25 x 1.25 degree) provided by the Japanese reanalysis (JRA-55; Kobayashi et al., 2015) and available at https://zenodo.org/record/8200832 (Gifford et al. 2023). For details see Gifford, 2023. 

    The wind stress curl (WSC) fields used for the MCL and ZCL calculations extend from 80W to 45W and 30N to 45N at the 1.25 by 1.25-degree resolution.  The MCL is defined as the maximum WSC values greater than zero within the domain per 1.25 degree longitude. As such, it is a function of longitude and is not a constant WSC value unlike the zero contour. High wind stress curl values that occurred near the coast were not included within this calculation. After MCL at the 1.25 resolution was obtained the line was smoothed with a gaussian smoothing and interpolated on to a 0.1 longitudinal resolution. The smoothed MCL lines at 0.1 degree resolution are provided in separate files for monthly and annual averages (2 files). Similarly, 2 other files (monthly and annual) are provided for the ZCL.    

    Like the MCL, the ZCL is a line derived from 1.25 degree longitude throughout the domain under the condition that it's the line of zero WSC. The ZCL is constant at 0 and does not vary spatially like the MCL. If there are more than one location of zero curl for a given longitude the first location south of the MCL is selected. Similar to the MCL, the ZCL was smoothed with a gaussian smoothing and interpolated on to a 0.1 longitudinal resolution.   

    The above files span the years from 1980 through 2019. So, the monthly files have 480 months starting January 1980, and the annual files have 40 years of data. The files are organized with each row being a new time step and each column being a different longitude. Therefore, the monthly MCL and ZCL files are each 480 x 351 for the 0.1 resolution data. Similarly, the annual files are 40 x 351 for the 0.1 degree resolution data.  

    Note that the monthly MCLs and ZCLs are obtained from the monthly wind-stress curl fields. The annual MCLs and ZCLs are obtained from the annual wind-stress curl fields.

    Since the monthly curl fields preserves more atmospheric mesoscales than the annual curl fields, the 12-month average of the monthly MCLs and ZCLs will not match with the annual MCLs and ZCLs derived from the annual curl field.  The annual MCLs and ZCLs provided here are obtained from the annual curl fields and representative metrics of the wind forcing on an annual time-scale. 

    Furthermore, the monthly Gulf Stream axis path (25 cm isoheight from Altimeter, reprocessed by Andres (2016) technique) from 1993 through 2019 have been made available here. A total of 324 monthly paths of the Gulf Stream are tabulated. In addition, the annual GS paths for these 27 years (1993-2019) of altimetry era have been put together for ease of use. The monthly Gulf Stream paths have been resampled and reprocessed for uniqueness at every 0.1 degree longitude from 75W to 50W and smoothed with a 100 km (10 point) running average via matlab. The uniqueness has been achieved by using Consolidator algorithm (D’Errico, 2023). 

    Each monthly or annual GS path has 251 points between 75W to 50W at 0.1 degree resolution.  

    Please contact igifford@earth.miami.edu for any queries. {"references": ["Andres, M., 2016. On the recent destabilization of the Gulf Stream path downstream of Cape Hatteras. Geophysical Research Letters, 43(18), 9836-9842.", "D'Errico, J., 2023. Consolidator (https://www.mathworks.com/matlabcentral/fileexchange/ 8354-consolidator), MATLAB Central File Exchange. Retrieved June 17, 2023.", "Gifford, Ian. H., 2023. The Synchronicity of the Gulf Stream Free Jet and the Wind Induced Cyclonic Vorticity Pool. MS Thesis, University of Massachusetts Dartmouth. 75pp.", "Gifford, Ian, H., Avijit Gangopadhyay, Magdalena Andres, Glen Gawarkiewicz, Hilde Oliver, Adrienne Silver, 2023. Wind Stress, Wind Stress Curl, and Upwelling Velocities in the Northwest Atlantic (80-45W, 30-45N) during 1980-2019, https://zenodo.org/record/8200832.", "Kobayashi, S., Ota, Y., Harada, Y., Ebita, A., Moriya, M., Onoda, H., Onogi, K., Kamahori, H., Kobayashi, C., Endo, H. and Miyaoka, K., 2015. The JRA-55 reanalysis: General specifications and basic characteristics.\u202fJournal of the Meteorological Society of Japan. Ser. II,\u202f93(1), pp.5-48. Kobayashi, S., Ota, Y., Harada, Y., Ebita, A., Moriya, M., Onoda, H., Onogi, K., Kamahori, H., Kobayashi, C., Endo, H. and Miyaoka, K., 2015. The JRA-55 reanalysis: General specifications and basic characteristics.\u202fJournal of the Meteorological Society of Japan. Ser. II,\u202f93(1), pp.5-48."]} 
    more » « less
  3. 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
  4. 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
  5. Summary

    We introduce a path following algorithm for L1-regularized generalized linear models. The L1-regularization procedure is useful especially because it, in effect, selects variables according to the amount of penalization on the L1-norm of the coefficients, in a manner that is less greedy than forward selection–backward deletion. The generalized linear model path algorithm efficiently computes solutions along the entire regularization path by using the predictor–corrector method of convex optimization. Selecting the step length of the regularization parameter is critical in controlling the overall accuracy of the paths; we suggest intuitive and flexible strategies for choosing appropriate values. We demonstrate the implementation with several simulated and real data sets.

     
    more » « less