Path Finding with RoadMap Algorithm on Multi-Agent

Object/目的

This is the final project of Geometric Reasoning and Applications course. In this project I implemented a multi-agent motion planning with roadmap algorithm. Each agent has its own attributes, such as, velocity, rigid body size, view field…etc. The start and goal positions are randomly generated. It also has simple collision avoidance. I also used MVC structure to implement a platform that can change the planning algorithm easily.

此為幾何推理分析課程的期末專案,這個專案使用Roadmap演算法的方式,實作多人的路徑規劃。在這個專案中,每個人都有不同的屬性,如:速度、身體大小、視野等等。其起點與終點目前是隨機方式產生,並賦予簡單的碰撞避免。在實作的部分用了MVC的架構開發了一個可以抽換不同Planner的平台。

Path Finding/路徑搜尋流程

We first randomly spread the point in collision free area of the planar map. After those points are set, we can specify the length, so that for each to points’ distance equal or less than the length can be connected together to form a roadmap. Currently, each agent is a circle shaped and its start and goal position are on the points spread before. With this roadmap, we can find a path by applying several path finding algorithms.

首先取得環境資訊後,在可以行走的空間中隨機灑點。在灑好這些點後,給定一個指定長度,我們可以將任兩點之間的距離小於或等於此指定長度的節點連接起來,形成Roadmap。我們目前假設所有的人都是一個圓形,其起點與終點皆為隨機在RoadMap節點上的任意一點。而藉由此Roadmap,我們就可以規劃出路徑,讓這些人前往他們的目的地。

Result/成果


Random point to form a Roadmap (Left) and with agents on it (right)
隨機灑點產生之Roadmap(左)與放上不同的人做路徑規劃(右)

Discussions/討論

Currently, I only implemented simple collision avoidance, besides, random spread point may not spread equally on each part of the planar map which might led to invisible area of the map. However, the main effort of this project is MVC structure and the path finding module tis easy to change, so that I can apply different algorithm easily. Different algorithms provide different control panels. Finally, all the other agents run on different threads.

目前此路徑規劃僅有簡單的人之間的碰撞避免,此外隨機灑點偶爾會出現點的分布不均,導致有些地方無法到達。但此專案主要功效在於將結構製作成MVC架構,使其更有延展的可能性,亦可套用不同的路徑規劃的演算法模型,右側的模型操作面板也能隨之更換。此外多人路徑規劃也應用Thread來實作。