(pp. 233-)
\nLet T be on of the trees rooted at qinit and qgoal.
\nAt each iteration, a random configuration q_rand is sampled uniformly in Q_free. The nearest configuration to q_rand in T, q_near, is found and an attempt is made to progress from q_near towards q_rand. Usually, this entails moving q_near a distance step_size in the straight line define by q_near and q_free. The newly generated config, q_new, if it is collision-free, is added to T, as well as the edge (q_near, q_new).
", "tags": [ { "tag": "RRT (rapidly-exploring random tree)" } ], "relations": {}, "dateAdded": "2013-09-25T13:10:16Z", "dateModified": "2013-09-25T13:10:16Z" } }, { "key": "NZ52NPGR", "version": 2, "library": { "type": "group", "id": 215753, "name": "Robotics - Motion Planning", "links": { "alternate": { "href": "https://www.zotero.org/groups/robotics_-_motion_planning", "type": "text/html" } } }, "links": { "self": { "href": "https://api.zotero.org/groups/215753/items/NZ52NPGR", "type": "application/json" }, "alternate": { "href": "https://www.zotero.org/groups/robotics_-_motion_planning/items/NZ52NPGR", "type": "text/html" }, "up": { "href": "https://api.zotero.org/groups/215753/items/6I2S4QE5", "type": "application/json" } }, "meta": { "createdByUser": { "id": 106785, "username": "pnfonseca", "name": "Pedro Fonseca", "links": { "alternate": { "href": "https://www.zotero.org/pnfonseca", "type": "text/html" } } }, "numChildren": 0 }, "data": { "key": "NZ52NPGR", "version": 2, "parentItem": "6I2S4QE5", "itemType": "note", "note": "(pg 219 e seguintes)
\nQRS aim to optimize various properties of the distribution of samples.
\nLet P be a set of point samples on some space X, and N=#P.
\nhow uniformly the points in P cover X
\nhow uniformly points are distributed over the space X; provides a measure of the largest portion of X that contains no points of P.
\nVan de Corput sequence: can only be used to sample the real line.
\nHalton sequence: generalizes the Van der Corput sequence to d dimensions.
\nWhen N is specified, a Hammersley sequence achieves the best possible asymptotic discrepancy.
", "tags": [ { "tag": "quasi-random" }, { "tag": "random processes" } ], "relations": {}, "dateAdded": "2013-09-25T13:10:16Z", "dateModified": "2013-09-25T13:10:16Z" } }, { "key": "CAJ66K33", "version": 2, "library": { "type": "group", "id": 215753, "name": "Robotics - Motion Planning", "links": { "alternate": { "href": "https://www.zotero.org/groups/robotics_-_motion_planning", "type": "text/html" } } }, "links": { "self": { "href": "https://api.zotero.org/groups/215753/items/CAJ66K33", "type": "application/json" }, "alternate": { "href": "https://www.zotero.org/groups/robotics_-_motion_planning/items/CAJ66K33", "type": "text/html" }, "up": { "href": "https://api.zotero.org/groups/215753/items/6I2S4QE5", "type": "application/json" } }, "meta": { "createdByUser": { "id": 106785, "username": "pnfonseca", "name": "Pedro Fonseca", "links": { "alternate": { "href": "https://www.zotero.org/pnfonseca", "type": "text/html" } } }, "numChildren": 0 }, "data": { "key": "CAJ66K33", "version": 2, "parentItem": "6I2S4QE5", "itemType": "note", "note": "(pp 202--...)
\nPRM divides planning in two phases: learning phase, during which a roadmap in Qfree is built; and the query phase, during which user-defined query configurations are connected with the precomputed roadmap. The nodes of the roadmap are configurations in Qfree and the edges of the roadmap correspond to free paths computed by a local planner.
\nThe basic PRM algorithm first constructs a roadmap in a probabilistic way for a given workspace.
\nInitially, the graph G = ( V , E ) is empty. The, repeatedly, a configuration is sampled from Q. if the configuration is collision-free, it is added to the roadmap. The process is repeated until N collision-free configurations have been sampled. For every node q ∈ V a set Nq of k closest neighbours to the configuration q is chosen from V. The local planner is called to connect q to each node q' ∈ Nq. Whenever successful in computing a feasible path between q and q', the edge ( q,q' ) is added to the roadmap.
PRM was originally presented as a multiple-query planner: the goal was to create a roadmap that captures the connectivity of Qfree and then answer multiple user-defined queries very fast. In manyu planning instances, the answer to a single query is of interest and these instances are best served by single-query planners. Single-query planners attempt to solve a query as fast as possible and do not focus on the exploration of the entire Qfree. (pp 227)
", "tags": [ { "tag": "mobile robots" }, { "tag": "multiple-query planner" }, { "tag": "path planning" }, { "tag": "single-query planner" } ], "relations": {}, "dateAdded": "2013-09-25T13:10:16Z", "dateModified": "2013-09-25T13:10:16Z" } }, { "key": "AJ8UQUGB", "version": 2, "library": { "type": "group", "id": 215753, "name": "Robotics - Motion Planning", "links": { "alternate": { "href": "https://www.zotero.org/groups/robotics_-_motion_planning", "type": "text/html" } } }, "links": { "self": { "href": "https://api.zotero.org/groups/215753/items/AJ8UQUGB", "type": "application/json" }, "alternate": { "href": "https://www.zotero.org/groups/robotics_-_motion_planning/items/AJ8UQUGB", "type": "text/html" }, "up": { "href": "https://api.zotero.org/groups/215753/items/6I2S4QE5", "type": "application/json" } }, "meta": { "createdByUser": { "id": 106785, "username": "pnfonseca", "name": "Pedro Fonseca", "links": { "alternate": { "href": "https://www.zotero.org/pnfonseca", "type": "text/html" } } }, "numChildren": 0 }, "data": { "key": "AJ8UQUGB", "version": 2, "parentItem": "6I2S4QE5", "itemType": "note", "note": "Cap 10, 11, 12
", "tags": [ { "tag": "kinodynamic motion planning" } ], "relations": {}, "dateAdded": "2013-09-25T13:10:16Z", "dateModified": "2013-09-25T13:10:16Z" } }, { "key": "8ZIPCEKB", "version": 2, "library": { "type": "group", "id": 215753, "name": "Robotics - Motion Planning", "links": { "alternate": { "href": "https://www.zotero.org/groups/robotics_-_motion_planning", "type": "text/html" } } }, "links": { "self": { "href": "https://api.zotero.org/groups/215753/items/8ZIPCEKB", "type": "application/json" }, "alternate": { "href": "https://www.zotero.org/groups/robotics_-_motion_planning/items/8ZIPCEKB", "type": "text/html" }, "up": { "href": "https://api.zotero.org/groups/215753/items/6I2S4QE5", "type": "application/json" } }, "meta": { "createdByUser": { "id": 106785, "username": "pnfonseca", "name": "Pedro Fonseca", "links": { "alternate": { "href": "https://www.zotero.org/pnfonseca", "type": "text/html" } } }, "numChildren": 0 }, "data": { "key": "8ZIPCEKB", "version": 2, "parentItem": "6I2S4QE5", "itemType": "note", "note": "ESTs were initially developed as an efficient single-query planner that covers the space between qinit and qgoal rapidly. EST was initially geared toward kinodynamic problems.
\nLet T be on of the trees rooted at qinit and qgoal. The planner first selects a configuration q in T from which to grow T and then samples a random configuration, q_rand from a uniform distribution in the neighbourhood of q. Configuration q is selected at random with probability π(q).
\nThe local planner attemps a connection between q and q_rand. If sucessful, qrand is added to the vertices of T and (q,qrand) is added to the edges of T. A new configuration is added only if the planner succeeds in connecting it to an existing configuration in T.
\nπ(q) is biased towards configurations of T that are not dense.
\n(pp- 230-)
", "tags": [ { "tag": "EST (expansive search tree)" } ], "relations": {}, "dateAdded": "2013-09-25T13:10:16Z", "dateModified": "2013-09-25T13:10:16Z" } } ]