✍ Scribed by Ian Pratt
No coin nor oath required. For personal study only.
The problem of finding an optimal route between two points in a space strewn with obstacles has been extensively studied in robotics. The standard approach to such problems is first to reduce the original geometrical specification to a finite graph of possible routes, and then to use graph-searching techniques together with the metrical information available in the original geometrical specification to select the best of these routes. The algorithm presented here, by contrast, employs a "first-past-thepost" approach to route planning. Specifically, we show that the algorithm is guaranteed to produce a route satisfying a certain criterion of "sensibleness", because routes failing this criterion are always slower to get constructed. The approach taken here differs in three respects from most current work on route planning: (i) it finds sensible, but not necessarily optimal, routes; (ii) it is uninfluenced by perspective (though it is limited by occlusion problems); (iii) it produces its output in a qualitative form, which is nevertheless well-suited to guide the appropriate route-following behaviour.
📜 SIMILAR VOLUMES
A strongly polynomial time algorithm is described to solve the node-capacitated routing problem in an undirected ring network.
A method of determining the most effective way to joint lines in an optical distribution network is needed, because of the high cost of jointing optical-fiber lines compared to lines in a metallic network and because of the limitation on the number of joints. In this paper, I model the joint form pl