کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
413254 | 680382 | 2011 | 14 صفحه PDF | دانلود رایگان |
Inspired by the Witkowski’s algorithm, we introduce a novel path planning and replanning algorithm — the two-way D∗ (TWD∗) algorithm — based on a two-dimensional occupancy grid map of the environment. Unlike the Witkowski’s algorithm, which finds optimal paths only in binary occupancy grid maps, the TWD∗ algorithm can find optimal paths in weighted occupancy grid maps. The optimal path found by the TWD∗ algorithm is the shortest possible path for a given occupancy grid map of the environment. This path is more natural than the path found by the standard D∗ algorithm as it consists of straight line segments with continuous headings. The TWD∗ algorithm is tested and compared to the D∗ and Witkowski’s algorithms by extensive simulations and experimentally on a Pioneer 3DX mobile robot equipped with a laser range finder.
► The two-way D∗ algorithm finds optimal paths in weighted graphs.
► TWD∗ produces shorter and more natural low-cost paths through the grid.
► The TWD∗ path consists of straight line segments with continuous headings.
► The TWD∗ path is the shortest possible path in geometrical space.
► TWD∗ performs well in changing environments.
Journal: Robotics and Autonomous Systems - Volume 59, Issue 5, May 2011, Pages 329–342