Adaptive Path Planner for Highly Dynamic Environments
This paper describes adaptive path planning, a novel approach to path planning for car-like mobile robots. Instead of creating a new plan from scratch, whenever changes in the environment invalidate the current plan, the adaptive path planner attempts to
- PDF / 534,771 Bytes
- 10 Pages / 451 x 677.3 pts Page_size
- 10 Downloads / 254 Views
[email protected] http://www.citr.auckland.ac.nz/~jacky
Abstract. This paper describes adaptive path planning, a novel approach to path planning for car-like mobile robots. Instead of creating a new plan from scratch, whenever changes in the environment invalidate the current plan, the adaptive path planner attempts to adapt the old plan to the new situation. The paper proposes an eÆcient representation for path that is easily amendable to adaptation. Associated with the path planner is a set of repair strategies. These repair strategies are local methods to x a plan to compensate for object movement in the domain. The repair strategies are speci c and have a high probability of being able to x a plan. An empirical evaluation shows that adaptive path planning is suitable to highly dynamic domains, such as RoboCup. Adaptive path planning reduces the cumulative planning time by a factor of 2:7 compared to Bicchi's planner. At the same time, the quality of the plans generated by the adaptive path planner were similar to those generated by Bicchi's planner.
1
Introduction
Navigation is an important task for any mobile robot. Before a robot can a ect the world in any sensible way, it must be at the right place at the right time. The navigation task can be broken down into a number of important sub tasks: localization, path planning, and plan execution. Path planning is the problem of creating a collision free path through a set of obstacles from an initial to a goal position. A simple example is planning to go from the entrance of the CITR lab to the desk in room 305 on the third oor. Path planners can be categorized based on whether global or local information about the environment is available and whether objects are static or dynamic. The F180 league in RoboCup, a game of soccer between autonomous robots, is a good example of a global path planning domain with dynamic obstacles. The RoboCup domain has a number of properties, which makes it interesting for real world planning. It features a high density of highly dynamic obstacles. This means that an agent has to re-plan often, since plans may be invalidated through objects moving. In fact, RoboCup features an active opponent that tries P. Stone, T. Balch, and G. Kraetzschmar (Eds.): RoboCup 2000, LNAI 2019, pp. 76-85, 2001. c Springer-Verlag Berlin Heidelberg 2001
Adaptive Path Planner for Highly Dynamic Environments
77
to prev ent a robot from executing its plan (e.g., a defender tries to prevent a strik er from moving into a position in front of the goal) successfully. A robot designed to perform real world applications, such as search and rescue in dangerous en vironments will have to cope with similar environments. A path planner in such a domain needs to be able to react quickly to changes in the environment. F urthermore, the path planner needs to be able to return at least an approximate plan (a best guess) immediately, that is it must be an anytime path planner. On the other hand, as more planning time is available, a better plan should be retur
Data Loading...
