Multi planner Search - shivamvats/notes GitHub Wiki

Factor the search space into subspaces such that their Cartesian product is the original search space. For example,

X = A x B

The factorization should be done on the basis of some prior about the environment. For example, consider an arm mounted atop a holonomic base. It is clear than the dofs controlling the arm are useful towards the end of the plan. Hence, encoding a prior to this effect so that search effort is directed towards the base dofs in the initial phase of search is expected to be useful.

Similarly, in the case of motion planning for a humanoid, we can usually do without manipulation of the arms if the environment is largely clutter free. This is something that can be inferred from the perception data.

Treat the problem of choosing which queue(factor) to spawn as a multi-armed bandit problem.

Start search with some factor (say x, y, yaw). During search, keep track of the successors being generated. If many of the successors being generated are invalid (say due to collision), this gives us some information about relevant dof's we might want to change. For example, if a lot of successors are invalid due to arm-world collision, we might want to spawn the factor controlling the arm.

Why does humanoid motion planning suck?

Because we do not leverage Physics. We do not leverage the fact that if our arm is colliding with obstacles, the "shoulder" joint is the most important joint to be modified. Not all joints are of equal importance!

Level 1 We should be able to reason about the dynamics model. For example, I should know in some form that actuating the shoulder changes the arm dofs, etc. I should know the cause-effect relationship among dofs. With this knowledge, I can make use of information about the robot's collisions with the environment.

Level 2 A human does not wait for an actual collision to happen. He predicts a collision if it is likely and takes mitigating actions. Similarly, the robot should be able to predict that the likelihood of collision of certain part of the robot is high in the near future and take appropriate action by actuating the relevant dofs.

Once the planner is stuck in a local minimum, we spawn queues for the other factors (something like Dynamic MHA*).