Terrain path planning

2015

• Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Fast path planning under polygonal obstacle constraints. In 4th GIS-focused algorithm competition, GISCUP 2015, co-located with ACM SIGSPATIAL GIS. Bellevue WA USA, 4 Nov 2015. Winner (2nd place).
  [details] [full text] [BibTeX▼]

  @inproceedings{salles-giscup-2015,
      author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
      title = "Fast path planning under polygonal obstacle constraints",
      booktitle = "4th {GIS}-focused algorithm competition, {GISCUP} 2015, co-located with {ACM SIGSPATIAL GIS}",
      year = "2015",
      month = "4 Nov",
      address = "Bellevue WA USA",
      note = "Winner (2nd place)",
      mykey = "wenlili marcus salles pathplan sallesgiscup2015 uplan",
      href = "\bibhref{203-salles-giscup-2015}"
  }
  

2008

• Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler, Franklin T. Luk, Marcus Andrade, and Jared Stookey. Path planning on a compressed terrain. In Walid G. Aref and others, editors, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). Irvine CA, 5–7 Nov 2008. (poster and fast forward presentation). URL: http://acmgis08.cs.umn.edu/.
  [details] [full text] [slides] [poster] [BibTeX▼]

  @inproceedings{tracy-acmgis-2008,
      author = "Tracy, Daniel M. and Franklin, W. Randolph and Cutler, Barbara and Luk, Franklin T. and Andrade, Marcus and Stookey, Jared",
      editor = "Aref, Walid G. and others",
      title = "Path Planning on a Compressed Terrain",
      booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)",
      year = "2008",
      address = "Irvine CA",
      month = "5--7 Nov",
      customlinkslides = "https://wrfranklin.org/p/124-acmgis2008-tracy-talk.pdf",
      customlinkposter = "https://wrfranklin.org/p/124-acmgis2008-tracy-poster.pdf",
      mykey = "pathplan marcus tracy",
      href = "\bibhrefpttpp{124-acmgis2008-tracy}",
      note = "(poster and fast forward presentation)",
      url = "http://acmgis08.cs.umn.edu/"
  }
  

• Daniel M. Tracy, W Randolph Franklin, Barb Cutler, Franklin Luk, Marcus Andrade, and Jared Stookey. Path planning on complex terrain. In 18th Fall Workshop on Computational Geometry (FWCG 2008). Rensselaer Polytechnic Institute, Troy NY USA, 31 Oct – 1 Nov 2008. (extended abstract, talk and poster).
  [details] [full text] [slides] [poster] [BibTeX▼]

  @inproceedings{tracy-fwcg-2008,
      author = "Tracy, Daniel M. and Franklin, W Randolph and Cutler, Barb and Luk, Franklin and Andrade, Marcus and Stookey, Jared",
      title = "Path Planning on Complex Terrain",
      booktitle = "18th Fall Workshop on Computational Geometry ({FWCG} 2008)",
      month = "31 Oct -- 1 Nov",
      year = "2008",
      note = "(extended abstract, talk and poster)",
      address = "Rensselaer Polytechnic Institute, Troy NY USA",
      customlinkslides = "https://wrfranklin.org/p/128-fwcg2008-tracy-talk.ppt",
      customlinkposter = "https://wrfranklin.org/p/128-fwcg2008-tracy-poster.ppt",
      mykey = "pathplan marcus tracy",
      href = "\bibhrefatp{128-fwcg2008-tracy}{128-fwcg2008-tracy-talk.ppt}{128-fwcg2008-tracy-poster.ppt}"
  }
  

• W. Randolph Franklin, Daniel M. Tracy, Marcus Andrade, Jonathan Muckell, Metin Inanc, Zhongyi Xie, and Barbara Cutler. Slope accuracy and path planning on compressed terrain. In Symposium on Spatial Data Handling. Montpellier FR, June 2008.
  [details] [full text] [BibTeX▼]

  @inproceedings{wrf-sdh-2008,
      author = "Franklin, W. Randolph and Tracy, Daniel M. and Andrade, Marcus and Muckell, Jonathan and Inanc, Metin and Xie, Zhongyi and Cutler, Barbara",
      title = "Slope Accuracy and Path Planning on Compressed Terrain",
      booktitle = "Symposium on Spatial Data Handling",
      year = "2008",
      month = "June",
      address = "Montpellier FR",
      mykey = "tracy inanc marcus muckell xie pathplan terrain",
      href = "\bibhref{119-sdh08-slope}"
  }
  

2007

• W Randolph Franklin, Metin Inanc, Zhongyi Xie, Daniel M. Tracy, Barbara Cutler, Marcus V A Andrade, and Franklin Luk. Smugglers and border guards – the GeoStar project at RPI. In 15th ACM International Symposium on Advances in Geographic Information Systems (ACM GIS 2007). Seattle, WA, USA, Nov 2007.
  [abstract▼] [details] [full text] [slides] [BibTeX▼]

  We present the GeoStar project at RPI, which researches various terrain (i.e., elevation) representations and operations thereon. This work is motivated by the large amounts of hi-res data now available. The purpose of each representation is to lossily compress terrain while maintaining important properties. Our ODETLAP representation generalizes a Laplacian partial differential equation by using two inconsistent equations for each known point in the grid, as well as one equation for each unknown point. The surface is reconstructed from a carefully chosen small set of known points. Our second representation segments the terrain intoa set of regions, each of which is simply described. Our third representation has the most long term potential: scooping, which forms the terrain by emulating surface water erosion. Siting hundreds of observers, such as border guards, so that their viewsheds jointly cover the maximum terrain is our first operation. This process allows both observer and target to be above the local terrain, and the observer to have a finite radius of interest. Planning a path so that a smuggler may get from point A to point B while maximally avoiding the border guards is our second operation. The path metric includes path length, distance traveled uphill,and amount of time visible to a guard. The quality of our representations is determined, not only by their RMS elevation error, but by how accurately they support these operations.

  @inproceedings{acmgis07,
      author = "Franklin, W Randolph and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M. and Cutler, Barbara and Andrade, Marcus V A and Luk, Franklin",
      title = "Smugglers and border guards -- the {GeoStar} project at {RPI}",
      booktitle = "15th {ACM} International Symposium on Advances in Geographic Information Systems {(ACM GIS 2007)}",
      year = "2007",
      address = "Seattle, WA, USA",
      month = "Nov",
      customlinkslides = "https://wrfranklin.org/p/115-seattle07-acmgis-smugglers-talk.ppt",
      mykey = "pathplan visviewshedsiting marcus tracy inanc xie",
      href = "\bibhrefpt{115-seattle07-acmgis-smugglers}{115-seattle07-acmgis-smugglers-talk.ppt}"
  }
  

• Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler, Marcus A Andrade, Franklin T Luk, Metin Inanc, and Zhongyi Xie. Multiple observer siting and path planning on lossily compressed terrain. In Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII. San Diego CA, 27 August 2007. International Society for Optical Engineering. paper 6697-16.
  [abstract▼] [details] [full text] [BibTeX▼]

  We examine a smugglers and border guards scenario. We place observers on a terrain so as to optimize their visible coverage area. Then we compute a path that a smuggler would take so as to avoid detection, while also minimizing the path length. We also examine how our results are affected by using a lossy representation of the terrain instead. We propose three new application-specific error metrics for evaluating terrain compression. Our target terrain applications are the optimal placement of observers on a landscape and the navigation through the terrain by smugglers. Instead of using standard metrics such as average or maximum elevation error, we seek to optimize our compression on the specific real-world application of smugglers and border guards.

  @inproceedings{dt-wrf-spie-2007,
      author = "Tracy, Daniel M. and Franklin, W. Randolph and Cutler, Barbara and Andrade, Marcus A and Luk, Franklin T and Inanc, Metin and Xie, Zhongyi",
      title = "Multiple observer siting and path planning on lossily compressed terrain",
      booktitle = "Proceedings of {SPIE} Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations {XVII}",
      year = "2007",
      month = "27 August",
      organization = "International Society for Optical Engineering",
      address = "San Diego CA",
      note = "paper 6697-16",
      mykey = "inanc tracy marcus xie pathplan visviewshedsiting",
      href = "\bibhref{114-spie07-tracy}"
  }
  

2006

• W. Randolph Franklin. Smugglers' path planning on compressed terrain. talk at UniGIS conference, May 2006.
  [details] [slides] [BibTeX▼]

  @misc{unigis-2006,
      author = "Franklin, W. Randolph",
      title = "Smugglers' path planning on compressed terrain",
      howpublished = "talk at {UniGIS} conference",
      organization = "Simon Fraser University",
      address = "Vancouver, Canada",
      month = "May",
      year = "2006",
      mykey = "pathplan",
      customlinkslides = "https://wrfranklin.org/p/158-unigis06-smugglers.ppt",
      href = "\bibhreft{158-unigis06-smugglers.ppt}"
  }
  

1987

• Wm Randolph Franklin and V. Akman. A workbench to compute unobstructed shortest paths in three-space. In Proc. 1st Internat. Conf. Indust. Applied Math., 1–38. Paris, France, 1987.
  [details] [full text] [BibTeX▼]

  @inproceedings{fa-wcusp-87,
      author = "Franklin, Wm Randolph and Akman, V.",
      title = "A workbench to compute unobstructed shortest paths in three-space",
      booktitle = "Proc. 1st Internat. Conf. Indust. Applied Math.",
      address = "Paris, France",
      year = "1987",
      pages = "1--38",
      oldlabel = "geom-1319",
      href = "\bibhref{36-siam87-shortest}",
      mykey = "akman pathplan",
      keywords = "motion planning"
  }
  

1986

• Varol Akman and W. Randolph Franklin. Locus techniques for shortest path problems in robotics. In IFAC Symposium on Robot Control (SYSROCO'85). Barcelona, 1986.
  [details] [full text] [BibTeX▼]

  @incollection{akman-barcelona-86,
      author = "Akman, Varol and Franklin, W. Randolph",
      title = "Locus Techniques for Shortest Path Problems in Robotics",
      booktitle = "IFAC Symposium on Robot Control (SYSROCO'85)",
      address = "Barcelona",
      year = "1986",
      href = "\bibhref{35-sysroco85-locus}",
      mykey = "akman pathplan"
  }
  

1985

• Wm Randolph Franklin and Varol Akman. Shortest paths in 3-space, Voronoi diagrams with barriers, and related complexity and algebraic issues. In Proceedings of the NATO Advanced Study Institute on Fundamental Algorithms for Computer Graphics, volume 17 of NATO ASI Series F, pages 895–917. Springer-Verlag, Ilkley, Yorkshire, England, 30 March – 12 April 1985.
  [details] [full text] [BibTeX▼]

  @incollection{fa-sp3sv-85,
      author = "Franklin, Wm Randolph and Akman, Varol",
      title = "Shortest Paths in 3-Space, {V}oronoi Diagrams with Barriers, and Related Complexity and Algebraic Issues",
      booktitle = "Proceedings of the {NATO} Advanced Study Institute on Fundamental Algorithms for Computer Graphics",
      address = "Ilkley, Yorkshire, England",
      month = "30 March -- 12 April",
      year = "1985",
      publisher = "Springer-Verlag",
      series = "{NATO} {ASI} Series F",
      volume = "17",
      pages = "895--917",
      href = "\bibhref{31-nato85-shortest}",
      mykey = "akman pathplan",
      keywords = "motion planning"
  }
  

• Wm Randolph Franklin and Varol Akman. Shortest paths in 3-space, Voronoi diagrams with barriers, and related complexity and algebraic issues. In L. Basañez, Gabriel A. Ferraté, and George N. Saridis, editors, Robot Control (SYROCO '85): Proceedings of the 1st IFAC Symposium, volume 1, pages 271–275. International Federation of Automatic Control, Barcelona, Spain, 6–8 November 1985.
  [details] [BibTeX▼]

  @incollection{fa-sp3sv-85a,
      author = "Franklin, Wm Randolph and Akman, Varol",
      editor = "Basañez, L. and Ferraté, Gabriel A. and Saridis, George N.",
      title = "Shortest Paths in 3-Space, {V}oronoi Diagrams with Barriers, and Related Complexity and Algebraic Issues",
      booktitle = "Robot Control ({SYROCO} '85): Proceedings of the 1st {IFAC} Symposium",
      address = "Barcelona, Spain",
      month = "6--8 November",
      year = "1985",
      volume = "1",
      publisher = "International Federation of Automatic Control",
      isbn = "0080334466, 9780080334462",
      pages = "271--275",
      xfulltext = "https://wrfranklin.org/p/31-nato85-shortest.pdf",
      xhref = "\bibhref{31-nato85-shortest}",
      mykey = "akman pathplan",
      keywords = "motion planning"
  }
  

• Wm Randolph Franklin, Varol Akman, and Colin Verrilli. Voronoi diagrams with barriers and on polyhedra for minimal path planning. Visual Comput., 1(2):133–150, October 1985.
  [details] [full text] [BibTeX▼]

  @article{fav-vdbpm-85,
      author = "Franklin, Wm Randolph and Akman, Varol and Verrilli, Colin",
      title = "Voronoi diagrams with barriers and on polyhedra for minimal path planning",
      journal = "Visual Comput.",
      volume = "1",
      number = "2",
      month = "October",
      year = "1985",
      pages = "133--150",
      oldlabel = "geom-1246",
      href = "\bibhref{18-vc85-voronoi}",
      mykey = "akman pathplan",
      keywords = "robotics, planar partitions, motion planning, Voronoi diagrams"
  }
  

• Varol Akman and W. Randolph Franklin. Partitioning the space to calculate shortest paths to any goal around polyhedral obstacles. In Proceedings of ROBEXS'85, the First Annual Workshop on Robotics and Expert Systems. NASA/Johnson Space Center, 27–28 June 1985.
  [details] [full text] [BibTeX▼]

  @inproceedings{akman-robexs-85,
      author = "Akman, Varol and Franklin, W. Randolph",
      title = "Partitioning the Space to Calculate Shortest Paths to any Goal Around Polyhedral Obstacles",
      booktitle = "Proceedings of ROBEXS'85, the First Annual Workshop on Robotics and Expert Systems",
      address = "NASA/Johnson Space Center",
      month = "27--28 June",
      year = "1985",
      href = "\bibhref{32-robexs85-shortest}",
      mykey = "pathplan akman"
  }
  

1984

• Wm Randolph Franklin and Varol Akman. Shortest paths between source and goal points located on/around a convex polyhedron. In 22nd Annual Allerton Conference on Communication, Control, and Computing. Urbana, Illinois, USA, 3–5 October 1984.
  [details] [full text] [BibTeX▼]

  @inproceedings{fa-spsgo-84,
      author = "Franklin, Wm Randolph and Akman, Varol",
      title = "Shortest Paths Between Source and Goal Points Located On/Around a Convex Polyhedron",
      booktitle = "22nd Annual Allerton Conference on Communication, Control, and Computing",
      month = "3--5 October",
      year = "1984",
      address = "Urbana, Illinois, USA",
      href = "\bibhref{26-allerton84-shortest}",
      mykey = "akman pathplan",
      keywords = "motion planning"
  }