{"id":{"repo_id":"unr","oai_identifier":"oai:scholarwolf.unr.edu:11714/3641"},"canonical_url":"https://search.dev.ndltd.org/etd/unr/oai:scholarwolf.unr.edu:11714/3641","repository":{"repo_id":"unr","name":"University of Nevada - Reno","base_url":"https://scholarwolf.unr.edu/server/oai/request"},"display":{"title":"Provably Asymptotically Near-Optimal Motion Planning with Sparse Data Structures","abstract":"Asymptotically optimal planners, such as PRM*, guarantee thatsolutions approach optimal as iterations increase. Roadmaps with this property, however, may grow too large. If optimality is relaxed,asymptotically near-optimal solutions produce sparser graphs by notincluding all edges. The idea stems from graph spanner algorithms,which produce sparse subgraphs that guarantee near-optimal paths.Existing asymptotically optimal and near-optimal planners, however,include all sampled configurations as roadmap nodes. Consequently, only infinite graphs have the desired properties. This work proposes an approach that provides the following asymptotic properties: (a) completeness, (b) near-optimality and (c) the probability of adding nodes to the spanner roadmap converges to zero as iterations increase. Thus, the method suggests that finite-size data structures might have near-optimality properties. The method brings together ideas from various planners but deviates from existing integrations of PRM* with graph spanners. Simulations for rigid bodies show that the method indeed provides small roadmaps and results in faster query resolution. The rate of node addition is shown to decrease over time and the quality of solutions satisfies the theoretical bounds. Smoothing provides a more favorable comparison against alternatives with regards to path length.","abstract_html":"Asymptotically optimal planners, such as PRM*, guarantee thatsolutions approach optimal as iterations increase. Roadmaps with this property, however, may grow too large. If optimality is relaxed,asymptotically near-optimal solutions produce sparser graphs by notincluding all edges. The idea stems from graph spanner algorithms,which produce sparse subgraphs that guarantee near-optimal paths.Existing asymptotically optimal and near-optimal planners, however,include all sampled configurations as roadmap nodes. Consequently, only infinite graphs have the desired properties. This work proposes an approach that provides the following asymptotic properties: (a) completeness, (b) near-optimality and (c) the probability of adding nodes to the spanner roadmap converges to zero as iterations increase. Thus, the method suggests that finite-size data structures might have near-optimality properties. The method brings together ideas from various planners but deviates from existing integrations of PRM* with graph spanners. Simulations for rigid bodies show that the method indeed provides small roadmaps and results in faster query resolution. The rate of node addition is shown to decrease over time and the quality of solutions satisfies the theoretical bounds. Smoothing provides a more favorable comparison against alternatives with regards to path length.","abstract_has_math":false,"creators":["Dobson, Andrew J."],"institution":null,"degree_name":null,"degree_level":"Master's Degree","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Bekris, Kostas E."],"committee_chairs":[],"committee_members":["Nicolescu, Monica","Quint, Thomas","LaTourrette, Nancy"],"year":2012,"date_issued":"2012","date_published":"2012","updated_at":"2026-07-27T21:47:14Z","subjects":["Asymptotic","Asymptotically optimal","Motion Planning","Optimal","PRM","resource constrained"],"languages":[],"rights":["In Copyright(All Rights Reserved)"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11714/3641","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Bekris, Kostas E."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Nicolescu, Monica","Quint, Thomas","LaTourrette, Nancy"]},{"key":"dc:creator","label":"Author","values":["Dobson, Andrew J."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2018-07-26T18:17:38Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-07-26T18:17:38Z"]},{"key":"dc:date.issued","label":"Date","values":["2012"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Master's Degree"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Asymptotic","Asymptotically optimal","Motion Planning","Optimal","PRM","resource constrained"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright(All Rights Reserved)"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11714/3641"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Asymptotically optimal planners, such as PRM*, guarantee thatsolutions approach optimal as iterations increase. Roadmaps with this property, however, may grow too large. If optimality is relaxed,asymptotically near-optimal solutions produce sparser graphs by notincluding all edges. The idea stems from graph spanner algorithms,which produce sparse subgraphs that guarantee near-optimal paths.Existing asymptotically optimal and near-optimal planners, however,include all sampled configurations as roadmap nodes. Consequently, only infinite graphs have the desired properties. This work proposes an approach that provides the following asymptotic properties: (a) completeness, (b) near-optimality and (c) the probability of adding nodes to the spanner roadmap converges to zero as iterations increase. Thus, the method suggests that finite-size data structures might have near-optimality properties. The method brings together ideas from various planners but deviates from existing integrations of PRM* with graph spanners. Simulations for rigid bodies show that the method indeed provides small roadmaps and results in faster query resolution. The rate of node addition is shown to decrease over time and the quality of solutions satisfies the theoretical bounds. Smoothing provides a more favorable comparison against alternatives with regards to path length."]},{"key":"dc:format","label":"Dc Format","values":["PDF"]},{"key":"dc:title","label":"Title","values":["Provably Asymptotically Near-Optimal Motion Planning with Sparse Data Structures"]}]}],"canonical_facts":{"dc:contributor.advisor":["Bekris, Kostas E."],"dc:contributor.committeemember":["Nicolescu, Monica","Quint, Thomas","LaTourrette, Nancy"],"dc:creator":["Dobson, Andrew J."],"dc:date.accessioned":["2018-07-26T18:17:38Z"],"dc:date.available":["2018-07-26T18:17:38Z"],"dc:date.issued":["2012"],"dc:description.abstract":["Asymptotically optimal planners, such as PRM*, guarantee thatsolutions approach optimal as iterations increase. Roadmaps with this property, however, may grow too large. If optimality is relaxed,asymptotically near-optimal solutions produce sparser graphs by notincluding all edges. The idea stems from graph spanner algorithms,which produce sparse subgraphs that guarantee near-optimal paths.Existing asymptotically optimal and near-optimal planners, however,include all sampled configurations as roadmap nodes. Consequently, only infinite graphs have the desired properties. This work proposes an approach that provides the following asymptotic properties: (a) completeness, (b) near-optimality and (c) the probability of adding nodes to the spanner roadmap converges to zero as iterations increase. Thus, the method suggests that finite-size data structures might have near-optimality properties. The method brings together ideas from various planners but deviates from existing integrations of PRM* with graph spanners. Simulations for rigid bodies show that the method indeed provides small roadmaps and results in faster query resolution. The rate of node addition is shown to decrease over time and the quality of solutions satisfies the theoretical bounds. Smoothing provides a more favorable comparison against alternatives with regards to path length."],"dc:format":["PDF"],"dc:identifier.uri":["http://hdl.handle.net/11714/3641"],"dc:rights":["In Copyright(All Rights Reserved)"],"dc:subject":["Asymptotic","Asymptotically optimal","Motion Planning","Optimal","PRM","resource constrained"],"dc:title":["Provably Asymptotically Near-Optimal Motion Planning with Sparse Data Structures"],"dc:type":["Thesis"],"thesis:degree_level":["Master's Degree"]},"updated_at":"2026-07-27T21:47:14Z"}