Pacman problem using Tree Plus Rand Actions and ARA* as the base algorithm
I have some preliminary results on using ARA* as the base algorithm for metaplanning.
Since the ARA* algorithm is iterative, there is a question as to when to stop it. The way I set it up for these experiments was to stop the ARA* algorithm after the first iteration. This results in slightly longer paths, but reduces the time spent planning, which is the key to doing well in this domain. This is for the case of NO TUNNEL.
1. Although metaplanning with ARA* led to improvements over using A* as the base algorithm, these improvements were for the higher ghost speeds only.
2. It appears that for slower ghost speeds the metaplanning solution actually got worse.
3. When compared to planning with ARA* alone, metaplanning using ARA* still is not as good.
Our initial motivation for using ARA* rather than A* as the base level algorithm was because we noticed that ARA* could generate a path to the goal in less time than A* could generate a path for a single arc link. This resulted in longer time spent planning for the metaplanner using A* as the base algorithm.
4. Even after using ARA* as the base algorithm, the time taken to generate paths for individual are could still exceed the time taken for ARA* itself to generate a path to the goal.
5. Next I wanted to check that I wasn't losing anything by using ARA* on individual arc links. So I generated results for a min of all paths using ARA*.
These results showed confirm that using ARA* to compute paths for individual arc links is still more computationally costly than ARA* by itself. The average number of expansions for ARA* by itself on the first iteration is 66. The average number of expansions when using ARA* on individual arcs for the min of all paths experiment was 100.
For the min of all paths experiment I generate arcs in order from the start location to the goal location. I was curious as to whether the order of looking at arcs would affect the planning time.
6. I generated another set of data for min of all paths where I randomized the order of planning. It appears that this resulted in slightly degraded results.
7. Next I generated results for min of all paths with a mixed order which somewhat mimics the order dictated by the metaplanning policy. The results were comparable to to the others.
8. I then took a look as to why ARA* on individual arcs is so costly.
It appears that there are some obstacles and start and end locations that cause ARA* to spend a lot of time backtracking. It may be the concavity of the obstacles that causes ARA* to get stuck and needing the time to get itself out of the trap.
ARA* on the whole problem also experiences some of the same problems but since it is not constrained to plan along the arcs, tends to be able to avoid this problem much better than when it is constrained.
I am also worried that I may not be collecting enough data for the metaplanner to determine the right set of paths. I will try an experiment where I fix the initial ghost positions in order to generate the decision tree and transition probabilities, and will test the metaplanner on maps with the same initialization.
Since the ARA* algorithm is iterative, there is a question as to when to stop it. The way I set it up for these experiments was to stop the ARA* algorithm after the first iteration. This results in slightly longer paths, but reduces the time spent planning, which is the key to doing well in this domain. This is for the case of NO TUNNEL.
1. Although metaplanning with ARA* led to improvements over using A* as the base algorithm, these improvements were for the higher ghost speeds only.
2. It appears that for slower ghost speeds the metaplanning solution actually got worse.
3. When compared to planning with ARA* alone, metaplanning using ARA* still is not as good.
Our initial motivation for using ARA* rather than A* as the base level algorithm was because we noticed that ARA* could generate a path to the goal in less time than A* could generate a path for a single arc link. This resulted in longer time spent planning for the metaplanner using A* as the base algorithm.
4. Even after using ARA* as the base algorithm, the time taken to generate paths for individual are could still exceed the time taken for ARA* itself to generate a path to the goal.
5. Next I wanted to check that I wasn't losing anything by using ARA* on individual arc links. So I generated results for a min of all paths using ARA*.
These results showed confirm that using ARA* to compute paths for individual arc links is still more computationally costly than ARA* by itself. The average number of expansions for ARA* by itself on the first iteration is 66. The average number of expansions when using ARA* on individual arcs for the min of all paths experiment was 100.
For the min of all paths experiment I generate arcs in order from the start location to the goal location. I was curious as to whether the order of looking at arcs would affect the planning time.
6. I generated another set of data for min of all paths where I randomized the order of planning. It appears that this resulted in slightly degraded results.
7. Next I generated results for min of all paths with a mixed order which somewhat mimics the order dictated by the metaplanning policy. The results were comparable to to the others.
8. I then took a look as to why ARA* on individual arcs is so costly.
It appears that there are some obstacles and start and end locations that cause ARA* to spend a lot of time backtracking. It may be the concavity of the obstacles that causes ARA* to get stuck and needing the time to get itself out of the trap.
ARA* on the whole problem also experiences some of the same problems but since it is not constrained to plan along the arcs, tends to be able to avoid this problem much better than when it is constrained.
I am also worried that I may not be collecting enough data for the metaplanner to determine the right set of paths. I will try an experiment where I fix the initial ghost positions in order to generate the decision tree and transition probabilities, and will test the metaplanner on maps with the same initialization.
posted by Hon Fai at 10:11 AM
0 Comments:
Post a Comment
<< Home