{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T14:48:34Z","timestamp":1749221314150,"version":"3.33.0"},"reference-count":16,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2007,3,13]],"date-time":"2007-03-13T00:00:00Z","timestamp":1173744000000},"content-version":"vor","delay-in-days":6249,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Robotic Syst."],"published-print":{"date-parts":[[1990,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The use of graph search algorithms on a so called \u201cvisibility graph\u201d is a common approach to finding a minimum\u2010distance collision\u2010free path among polyhedral obstacles in a 2D environment. Complexity of the search can be greatly reduced by reducing the size of the graph. The focus of this article is to provide an algorithm aimed at constructing a<jats:italic>subvisibility<\/jats:italic>graph using only \u201cnecessary\u201d obstacles, i.e., excluding as many obstacles as possible whose vertices are never via points of the shortest collision\u2010free path.<\/jats:p>","DOI":"10.1002\/rob.4620070107","type":"journal-article","created":{"date-parts":[[2007,7,6]],"date-time":"2007-07-06T09:33:00Z","timestamp":1183714380000},"page":"129-137","source":"Crossref","is-referenced-by-count":23,"title":["An efficient algorithm for finding a collision\u2010free path among polyhedral obstacles"],"prefix":"10.1002","volume":"7","author":[{"given":"Li\u2010Chen","family":"Fu","sequence":"first","affiliation":[]},{"given":"Dong\u2010Yueh","family":"Liu","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,3,13]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"N. J.Nilsson \u201cA Mobile Automation: An Application of Artificial Intelligence Techniques \u201d inProc. Int. J. Conf. of Artificial Intelligence 1969 509\u2013520.","DOI":"10.21236\/ADA459660"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840436"},{"key":"e_1_2_1_4_2","first-page":"190","article-title":"Solving the Find\u2010Path Problem by Good Representation of Free Space","volume":"13","author":"Brooks R. A.","journal-title":"IEEE Trans. System, Man, and Cybernetics"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"J.Canny \u201cA Voronoi Method for the Piano\u2010Movers' Problem \u201d inIEEE Conf. Robotics and Automation 1985 pp.530\u2013535.","DOI":"10.1109\/ROBOT.1985.1087297"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"volume-title":"Path Relaxation: Path Planning for a Mobile Robot","year":"1984","author":"Torpe C. E.","key":"e_1_2_1_7_2"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676196"},{"key":"e_1_2_1_9_2","unstructured":"D. T.Lee \u201cProximity and Reachability in the Plane \u201d Ph.D. Dissertation University of Illinois at Urbana\u2010Champaign 1978."},{"key":"e_1_2_1_10_2","first-page":"13","article-title":"Computing the Visibility of N Line Segments in O(N 2) time","volume":"26","author":"Guibas L.","year":"1985","journal-title":"Theoret. Computer Science"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215014"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90044-4"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"C.Bajaj \u201cAn Efficient Parallel Solution for Euclidean Shortest Path in Three Dimensions \u201d inIEEE Conf. Robotics and Automation 1986 pp.1897\u20131900.","DOI":"10.1109\/ROBOT.1986.1087478"},{"key":"e_1_2_1_14_2","unstructured":"E.Koch \u201cPlanning the Robot Motion in a Binary Space \u201d M.S. Thesis Gainesville FL 1983."},{"key":"e_1_2_1_15_2","unstructured":"J.Mitchell \u201cPlanning Shortest Paths \u201d Ph.D. Dissertation Stanford University 1986."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"M.Montgomery D.Gaw andA.Meystel \u201cNavigation Algorithm for a Nested Hierarchical System of Robot Path Planning among Polyhedral Obstacles \u201d inIEEE Conf of Robotics and Automation 1987 pp.1616\u20131622.","DOI":"10.1109\/ROBOT.1987.1087801"},{"key":"e_1_2_1_17_2","unstructured":"C. H.Lin \u201cAlgorithms for Robot Motion Planning and Navigation \u201d Master Thesis Dept. of Computer Science and Information Engineering June 1989."}],"container-title":["Journal of Robotic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frob.4620070107","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rob.4620070107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T07:15:50Z","timestamp":1737184550000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rob.4620070107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,2]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,2]]}},"alternative-id":["10.1002\/rob.4620070107"],"URL":"https:\/\/doi.org\/10.1002\/rob.4620070107","archive":["Portico"],"relation":{},"ISSN":["0741-2223","1097-4563"],"issn-type":[{"type":"print","value":"0741-2223"},{"type":"electronic","value":"1097-4563"}],"subject":[],"published":{"date-parts":[[1990,2]]}}}