Motion planning for dynamic environments is clearly one of the main problems that needs to be solved for effective autonomous navigation. As shown by Ref and Sharir, the general problem is NP-Hard, which explains the continued efforts to find algorithms to cope with that complexity.
A much more overlooked but equally critical aspect of the problem is motion prediction. Motion planning algorithms assume the availability of previous knowledge about how every mobile object in the environment will move, an assumption which does not hold for a vast number of situations and environments. The alternative is to predict how objects will move and to use that prediction as the input of the motion planning algorithm.