John. Nice job with this. This seems more powerful. Question though. It seems like this approach requires more human knowledge to be injected into the solution -- i.e. your idea of using the roofs as the higher level search. Would that be a possible con? Have you heard of a hierarchical system where the planner discovers the higher level on its own?
As a general rule, some prior knowledge will typically allow us to make some improvements and optimizations, but hierarchical path planning should be achievable in a very generic solution. We could start with just the lowest level with all the waypoints, then based on the total number decide how many layers we want. Then, to build a higher level layer from the a lower one, Add one lower waypoint to the higher waypoint graph, and reject all other waypoints with in some range of the one you moved to the higher level, repeat until all waypoints have been copied to higher layer or rejected then continue the process copying some waypoints from the layer you just created to make higher levels.
@@JonathanBurnside Ok, by waypoints you mean like navigational points that end each "leg" of the journey. But with planning we start with actions, each with preConds and postConds -- so do you mean the postConds being the waypoints? That seems like it could work. The only question is your phrase "reject all other waypoints within some range of the one you moved to the higher level". Do we actually know a range of closeness looking at the postConds? You might end up having some very long or short segments given you don't know how the planning will end up, right?
@@mjkeith8748 Ah I see, I was thinking in terms of path planning for movement through a 2D/3D space where you appear to be trying to apply this to a form of Action Planning. That is a rather interesting idea, I've not thought about it before. With the spatial path planning case we can find navigational points that are highly connected in our graph, raise those to a higher level graph and they will act as an approximation of the other navigation points that where spatially nearby but were not selected to be moved to the higher level graph. Then when these higher level graph points are used, there may have actually been a better path that existed in the lower level graph but the higher level graph point will be fairly close, and whatever method is used for following the chosen path will tend to smooth out any irregularities. I'm not sure where to find the same sort of pattern with Action Planning. I would imagine we would need navigation points, whose actions postConds, or results, are fairly similar so that one could be chosen to approximate similar other options that would not be moved to the higher level graphs. I'm not sure if that will exist in most Action Mapping graphs, in my experience they tend to have sparser less interconnected graphs and would have fewer options for picking useful navigational points to raise to higher level graphs. Maybe the initial graph could be traversed many times in as close to your working environment as possible, while tracking how often particular nodes in the graph are traversed, then move all the most traversed nodes to a higher level graph and repeat the process until you stop getting performance gains in your search times?
@@JonathanBurnside Good points. I suppose in your case you want a system that learns over many runs of the same game where each run can have different initial conditions etc. Therefore having an agent capable of learning these higher-level way points might make the agent a better and better player over many runs. Thinking about your suggestion -- " track how often particular nodes in the graph are traversed, then move all the most traversed nodes to a higher level graph". I would agree, something like that could probably work if we credit those popular nodes, but would you need to bias it such that we give more/less "credit" based on the outcomes or those particular runs? For example, if a node is visited 8 times in 8 runs, resulting in 4 wins and 4 losses -- maybe we don't move this node to a higher level. But if another node is visited 6 times with 5 wins, then he has more credit and so he does move up. In my case, the agent is solving variations of logic problems, say for example, the farmer/sheep/wolf problem by finding the right sequence of actions (i.e. the right plan) to get to the desired goal state. Each "run" then is a similar but variant problem, generated to have both varied start states and different goal states -- in one case the goal is: get the farmer/wolf/sheep all to the other side of the stream, in another case the goal is: just get rid of the damn wolf, etc. For my effort, your idea of the most often visited nodes might work as well, but you might also need to bias credit based on the success or failure of the run. And, yeah, maybe I will let it fail (and negatively credit various nodes) and that might give it more information. Hmm, the more I type and consider all this, the more this is all starting to feel like Reinforcement learning (Q-Learning)..... Curious of your thoughts.
John. Nice job with this. This seems more powerful. Question though. It seems like this approach requires more human knowledge to be injected into the solution -- i.e. your idea of using the roofs as the higher level search. Would that be a possible con? Have you heard of a hierarchical system where the planner discovers the higher level on its own?
As a general rule, some prior knowledge will typically allow us to make some improvements and optimizations, but hierarchical path planning should be achievable in a very generic solution. We could start with just the lowest level with all the waypoints, then based on the total number decide how many layers we want. Then, to build a higher level layer from the a lower one, Add one lower waypoint to the higher waypoint graph, and reject all other waypoints with in some range of the one you moved to the higher level, repeat until all waypoints have been copied to higher layer or rejected then continue the process copying some waypoints from the layer you just created to make higher levels.
@@JonathanBurnside Ok, by waypoints you mean like navigational points that end each "leg" of the journey. But with planning we start with actions, each with preConds and postConds -- so do you mean the postConds being the waypoints? That seems like it could work. The only question is your phrase "reject all other waypoints within some range of the one you moved to the higher level". Do we actually know a range of closeness looking at the postConds? You might end up having some very long or short segments given you don't know how the planning will end up, right?
@@mjkeith8748 Ah I see, I was thinking in terms of path planning for movement through a 2D/3D space where you appear to be trying to apply this to a form of Action Planning. That is a rather interesting idea, I've not thought about it before.
With the spatial path planning case we can find navigational points that are highly connected in our graph, raise those to a higher level graph and they will act as an approximation of the other navigation points that where spatially nearby but were not selected to be moved to the higher level graph. Then when these higher level graph points are used, there may have actually been a better path that existed in the lower level graph but the higher level graph point will be fairly close, and whatever method is used for following the chosen path will tend to smooth out any irregularities.
I'm not sure where to find the same sort of pattern with Action Planning. I would imagine we would need navigation points, whose actions postConds, or results, are fairly similar so that one could be chosen to approximate similar other options that would not be moved to the higher level graphs. I'm not sure if that will exist in most Action Mapping graphs, in my experience they tend to have sparser less interconnected graphs and would have fewer options for picking useful navigational points to raise to higher level graphs.
Maybe the initial graph could be traversed many times in as close to your working environment as possible, while tracking how often particular nodes in the graph are traversed, then move all the most traversed nodes to a higher level graph and repeat the process until you stop getting performance gains in your search times?
@@JonathanBurnside Good points. I suppose in your case you want a system that learns over many runs of the same game where each run can have different initial conditions etc. Therefore having an agent capable of learning these higher-level way points might make the agent a better and better player over many runs.
Thinking about your suggestion -- " track how often particular nodes in the graph are traversed, then move all the most traversed nodes to a higher level graph". I would agree, something like that could probably work if we credit those popular nodes, but would you need to bias it such that we give more/less "credit" based on the outcomes or those particular runs? For example, if a node is visited 8 times in 8 runs, resulting in 4 wins and 4 losses -- maybe we don't move this node to a higher level. But if another node is visited 6 times with 5 wins, then he has more credit and so he does move up.
In my case, the agent is solving variations of logic problems, say for example, the farmer/sheep/wolf problem by finding the right sequence of actions (i.e. the right plan) to get to the desired goal state. Each "run" then is a similar but variant problem, generated to have both varied start states and different goal states -- in one case the goal is: get the farmer/wolf/sheep all to the other side of the stream, in another case the goal is: just get rid of the damn wolf, etc.
For my effort, your idea of the most often visited nodes might work as well, but you might also need to bias credit based on the success or failure of the run. And, yeah, maybe I will let it fail (and negatively credit various nodes) and that might give it more information. Hmm, the more I type and consider all this, the more this is all starting to feel like Reinforcement learning (Q-Learning).....
Curious of your thoughts.