The problem of path planning in unknown environments remains a challenging problem - as the environment is gradually observed during the navigation, the underlying planner has to update the environment representation and replan, promptly and constantly, to account for the new observations. In this paper, we present a visibility graph-based planning framework capable of dealing with navigation tasks in both known and unknown environments. The planner employs a polygonal representation of the environment and constructs the representation by extracting edge points around obstacles to form enclosed polygons. With that, the method dynamically updates a global visibility graph using a two-layered data structure, expanding the visibility edges along with the navigation and removing edges that become occluded by newly observed obstacles. When navigating in unknown environments, the method is attemptable in discovering a way to the goal by picking up the environment layout on the fly, updating the visibility graph, and fast re-planning corresponding to the newly observed environment. We evaluate the method in simulated and real-world settings. The method shows the capability to attempt and navigate through unknown environments, reducing the travel time by up to 12-47% from search-based methods: A*, D* Lite, and more than 24-35% than sampling-based methods: RRT*, BIT*, and SPARS.
翻译:未知环境中的路径规划问题仍是一个具有挑战性的问题 -- -- 随着导航过程中逐渐观测到环境,基本规划者必须迅速、持续地更新环境分布和重新规划,以说明新的观测结果。在本文件中,我们提出了一个能见的图形规划框架,能够处理已知和未知环境中的导航任务。规划者采用环境多边形代表,并通过在障碍周围提取边缘点以形成封闭多边形来构建代表。因此,该方法用两层数据结构来动态更新一个全球可见性图,在导航的同时扩大可见度边缘,并去除新观察到的障碍所隐蔽的边缘。在未知环境中航行时,该方法可以尝试通过在飞上采集环境布局、更新可见度图和快速重新规划来发现目标。我们在模拟和现实世界环境中评估了方法。该方法显示尝试和浏览未知环境的能力,将搜索方法的飞行时间减少到12.47%以上:A*、DPAR*、S-35和24以上方法。