Progress in Algorithmic Motion Planning and Opportunities at the Intersection with Perceptual Science. Kostas Bekris talk.

1. Interests:
   1. High-quality plans that
   2. Respect of physical constraints of the system
   3. Real time constraints are important
      1. Real-time planning may require short planning horizons which can lead to situations where collision cannot be avoided
   4. Multi-agent planning
   5. Interaction with humans
2. Methods cited for control theory: LQR, partial feedback linearization, HJB and pnotyagin’s principle
3. In late 70s, PSPACE-Hardness was established (Reif ’79, Schwartz & Sharir 82, 84)
4. Cites Canny’s work (I just grabbed his thesis from the library), talked about roadmaps, but the algorithm presented was doubly-exponential, never even implemented.
5. PRMs were introduced by Kavarki, Bekris’ advisor in 1996.  An efficient way of producing roadmaps
6. In the general case, planning without respecting dynamics and then trying to smooth the path so it complies with dynamics is not possible
7. He is interested in finding more computationally near-optimal results as opposed to optimal results at the limit with infinitely dense graphs
   1. Do dense planning and then prune
8. His general goal is PAC-style planning
   1. The results in the field are almost entirely at the limit
9. Under differential constraints, PRMs are difficult because of the BVP problem, RRTs dont have that problem
10. Methods of encouraging efficient exploration (otherwise acrobot for example just hangs down with random actions)
11. Can do replanning in domains that are non-static
12. Multi-agent path planning is poly-time (non-optimal) in discrete domains
13. Future work in area of co-robotics (robot, human interaction), maybe from perspective of game theory, but want pareto optimality, introduces a number of other problems, of course
14. They may get a BAXTER(!)
15. Minimax regret: Savage ’51, Niehas ’48
    1. Good for human interaction, because minimax results agree more with human intuition than game-theoretic results