Path planning based on potential fields from rough mereology
This paper focuses on path planning for a remote robotic agent using rough mereology potential field method. We test the proposed path-creation and path-finding algorithms and propose working alternative versions. Furthermore we apply path smoothing with custom collision detection to further optimize the route from the robot initial position to the goal.
The Square Fill algorithm was proposed by Osmialowski and Polkowski in Spatial Reasoning Based on Rough Mereology: A Notion of a Robot Formation and Path Planning Problem for Formations of Mobile Autonomous Robots, In: Transactions on Rough Sets XII. We used it as a base for our testing.
- Define initial values for
- Create an empty queue
- Add the first potential field to
- Enumerate through
- Check if the potential field is out of bounds or is colliding or already there,
- Increase the
current_distanceto the goal,
- Define neighbours depending on the
- Add neighbours to
- Change the
- Remove current potential field from
Qis empty, finish.
The default Square Fill Algorithm alternates between clockwise and anticlockwise methods while creating its potential ﬁeld neighbours. We experimented with possible outcomes:
- Clockwise variation,
- Anticlockwise variation.
Depending on the complexity of the map and placement of the robot, goal and obstacles diﬀerent results were produced. For a simple map containing two obstacles the following algorithm time and path length (in pixels) was returned:
- Path creation time: 2234.52 ms
- Total distance: 557.21 px
- Path creation time: 2370.07 ms
- Total distance: 540.86 px
- Path creation time: 2178.11 ms
- Total distance: 546.27 p
After the path from the robot initial position to the goal is created, we are applying a smoothing algorithm, to make the route optimal. We modiﬁed the standard smoothing algorithm, by adding custom conditions, to keep a safe distance from the robot to possible collision ﬁelds. The ﬁnal algorithm can be represented as:
def smooth_path(self, figure, path, alpha=0.1, beta=0.1, iterations=100): result = copy.deepcopy(path) # Copy not to alter the initial path for k in range(iterations): other = copy.deepcopy(result) for i in range(1, len(path) - 2): temp_x = result[i].x + alpha * (other[i-1].x + other[i+1].x - 2 * result[i].x) temp_x += beta * (other[i].x - result[i].x) temp_y = result[i].y + alpha * (other[i-1].y + other[i+1].y - 2 * result[i].y) temp_y += beta * (other[i].y - result[i].y) test_field = Field(x=temp_x, y=temp_y) should_be_added = True for coll in self.collision_coords: if test_field.distance_to(coll) < math.sqrt(math.pow(coll.r * 2, 2) + math.pow(coll.r * 2, 2)): should_be_added = False continue if should_be_added: result[i].x = temp_x result[i].y = temp_y self.draw_path(figure, result) self.path_points = result write_path_to_file(result)
- Zmudziński, L., Artiemjew, P.: Path planning based on potential fields from rough mereology, In: Proceedings of International Joint Conference on Rough Sets, IJCRS’17, Olsztyn, Poland, Lecture Notes in Computer Science (LNCS), vol. 10303, pp. 158-168. Springer, Heidelberg (2017)