利索能及
我要发布
收藏
专利号: 2023100920652
申请人: 浙江工业大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-07-29
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种室内区域中的实时导航方法,其特征在于,所述室内区域中的实时导航方法,包括:根据实际室内区域地图,将室内区域划分为若干个子区域,将整个室内区域抽象为连通图,每个子区域为连通图中的节点,每扇门为连通图中的边,将每扇门的平面坐标作为连通图中每条边的位置属性存储;

获取导航的起始子区域和终点子区域,在连通图中找到对应的起始节点和终点节点;

初始化连通图中的任意边和任意节点的属性;

将连通图中所有边放入最小堆,并根据边的属性进行排序,然后从最小堆中取出排序最小的边,开始搜索到达终点节点的路径,在每次搜索时更新下一跳边的属性和已访问节点的属性,直到搜索到终点节点,返回路径搜索结果,根据路径搜索结果进行导航;

其中,边的属性包括起始节点到本边的最短距离dist、本边的上一跳边及其属性prev、本边是否已被访问过e_visited、本边的位置pos和代价估计值eval;所述节点的属性包括本节点是否已被访问过v_visited;

所述根据边的属性进行排序,包括:

按照边的dist值与eval值之和的大小进行排序。

2.根据权利要求1所述的室内区域中的实时导航方法,其特征在于,所述将室内区域划分为若干个子区域,包括:将每个房间视为一个子区域,子区域之间通过门彼此连接。

3.根据权利要求1所述的室内区域中的实时导航方法,其特征在于,所述将室内区域划分为若干个子区域,包括:将狭长的区域和空旷区域划分为若干子区域,将子区域之间交界线中点的平面坐标作为连接子区域之间的门的坐标。

4.根据权利要求1所述的室内区域中的实时导航方法,其特征在于,所述初始化连通图中的任意边和任意节点的属性,包括:与起始节点直接相连的边的dist初始化为0,其余边的dist初始化为+∞;

边的prev初始化为空;

边的代价估计值eval,通过如下公式计算:

其中,Ed表示与终点节点d连接的所有边的集合,Es表示与起始节点s连接的所有边的集合,|Ed|表示集合Ed中的元素个数,|Es|表示集合Es中的元素个数;D(pos[e],pos[ei])表示边e的位置与边ei的位置之间的欧氏距离,β是经验参数;D(pos[s],pos[ei])表示与起始节点s相连的所有边的平均位置与边ei的位置之间的欧氏距离;

所有边的e_visited属性值初始化为未访问;

起始节点s的v_visited属性值初始化为已访问,其余节点的v_visited属性值初始化为未访问。

5.根据权利要求1所述的室内区域中的实时导航方法,其特征在于,所述从最小堆中取出排序最小的边,开始搜索到达终点节点的路径,在每次搜索时更新下一跳边的属性和已访问节点的属性,直到搜索到终点节点,返回路径搜索结果,包括:将排序最小的边表示为emin,如果emin的dist属性值为+∞,显示“终点不可达”,导航结束;

如果emin的dist属性值不为+∞,且emin不与终点节点d相连,则进一步判断emin连接的两个节点的v_visited属性值,如果v_visited属性值均为已访问,则将emin丢弃,重新从最小*堆中取出排序最小的边开始搜索;否则,得到emin连接的v_visited为未访问的节点v,将v_*visited[v]和e_visited[emin]标记为已访问;

如果emin的dist属性值不为+∞,且emin与终点节点d相连,则根据emin的prev属性值迭代查询,直到prev属性值为空,得到路径上所有边,此次路径搜索结束,返回路径搜索结果;

*

其中,在emin的dist属性值不为+∞,且emin不与终点节点d相连的情况中,还需要对v 做判断,包括:* *

若节点v与终点节点d连通,则令连接节点v和d的所有边为集合Ev*d,对于 计算emin的位置到e的位置之间的欧氏距离D(emin,e),如果dist[emin]+D(emin,e)

* *

若节点v与终点节点d不连通,则令连接节点v的所有边为集合Ev*,对于 且e的e_visited属性值为未访问,计算emin的位置到e的位置之间的欧氏距离D(emin,e),如果dist[emin]+D(emin,e)