一种迷宫搜索的方法

摘要

本发明涉及一种迷宫搜索的方法，该方法包括步骤如下：1)生成无方向概率距离图；2)生成有方向概率距离图；3)概率距离图的应用：建立步骤2）所述有方向概率距离图之后，机器人从起点迷宫格出发搜索迷宫，行进中遇到路口，根据机器人当前方向，利用概率距离图，判断哪个方向迷宫格的概率距离值最小，以此来决定行进路线,直到机器人抵达目标区域G。本发明将概率学中的概率与运动学中的距离有机的结合起来，提出了“概率距离”这一参数，以此参数为基准，使得迷宫搜索有理可据、有章可循。本发明实现了基于“概率距离”的迷宫搜索方法。

主权项

一种迷宫搜索的方法，其特征在于，该方法包括步骤如下：1)生成无方向概率距离图：迷宫中目标区域G为迷宫中心的四个相通的迷宫格，此目标区域G同外界相邻的是八个迷宫格，目标区域G必须与外界相通，虚线表示可能存在的墙壁，虚线围成的方格为迷宫格；假设初始时其他墙壁均不存在，迷宫格之间距离记为1，每一个90度转弯所耗时间也等效为距离，记为a，每一个180度转弯所耗时间等效为距离b，测试中所使用的机器人a≈1，b≈10；机器人所处的位置为迷宫格A，则迷宫格A和目标区域G的距离的计算方法为：距离迷宫格A最近的墙壁不存在的概率为p₁＝2⁷/(2⁸‑1)，此时迷宫格A到目标区域G的最短距离为s₁，即迷宫格A到目标区域G有p₁的可能距离为s₁；在所述最近的墙壁存在的情况下，距离迷宫格A第二近的墙壁不存在的概率p₂＝(1‑p₁)·2⁶/(2⁷‑1)，此时迷宫格A到目标区域G的最短距离为s₂，即迷宫格A到目标区域G有p₂的可能最短距离为s₂；依此类推，p_n、s_n；最终可得到迷宫格A到目标区域G的距离如(1)式：S_A＝p₁s₁+p₂s₂+p₃s₃+p₄s₄+p₅s₅+p₆s₆+p₇s₇+p₈s₈  (1)由于上述结果是一个概率与距离的乘积，表示概率意义上的距离，式(1)中的S_A为概率距离；2)生成有方向概率距离图：如机器人初始前进方向向上，则迷宫格B到目标区域G有p₁的可能最短距离为s_1dir；有p₂的可能最短距离为s_2dir；依次类推可以得到p_n、s_ndir；可得到迷宫格B到目标区域G的有向概率距离，如式(2)所示：$\begin{array}{c}{S}_{\mathrm{Bdir}}=p_1{s}_{1\mathrm{dir}}+p_2{s}_{2\mathrm{dir}}+p_3{s}_{3\mathrm{dir}}+p_4{s}_{s4\mathrm{dir}}+p_5{s}_{5\mathrm{dir}}+p_6{s}_{6\mathrm{dir}}+p_7{s}_{7\mathrm{dir}}+p_8{s}_{8\mathrm{dir}}\\ =2\frac{209}{255}+2\frac{134}{255}a\\ \approx 5\frac{88}{255}\end{array}---\left(2\right)$根据迷宫单元格的坐标进行编号，并按照上述算法进行计算，得出迷宫中每个单元格到目标区域的概率距离：当机器人初始方向为上时，按照上述计算和统计方式统计得“向上方向”的迷宫的概率距离图；同理，机器人初始方向为右时，将“向上方向”的迷宫的概率距离图顺时针旋转90°，保持坐标不变，仅数值变动；机器人初始方向为下时，将“向上方向”的迷宫的概率距离图顺时针旋转180°相同，保持坐标不变，仅数值变动；机器人方向为左时，将“向上方向”的迷宫的概率距离图逆时针旋转90°相同，保持坐标不变，仅数值变动；3)概率距离图的应用建立步骤2)所述有方向概率距离图之后，机器人从起点迷宫格出发搜索迷宫，行进中遇到路口，根据机器人当前方向，利用概率距离图，判断哪个方向迷宫格的概率距离值最小，以此来决定行进路线,直到机器人抵达目标区域G。