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

Interests:

High-quality plans that

Respect of physical constraints of the system

Real time constraints are important

Real-time planning may require short planning horizons which can lead to situations where collision cannot be avoided

Multi-agent planning

Interaction with humans

Methods cited for control theory: LQR, partial feedback linearization, HJB and pnotyagin’s principle

In late 70s, PSPACE-Hardness was established (Reif ’79, Schwartz & Sharir 82, 84)

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.

PRMs were introduced by Kavarki, Bekris’ advisor in 1996. An efficient way of producing roadmaps

In the general case, planning without respecting dynamics and then trying to smooth the path so it complies with dynamics is not possible

He is interested in finding more computationally near-optimal results as opposed to optimal results at the limit with infinitely dense graphs

Do dense planning and then prune

His general goal is PAC-style planning

The results in the field are almost entirely at the limit

Under differential constraints, PRMs are difficult because of the BVP problem, RRTs dont have that problem

Methods of encouraging efficient exploration (otherwise acrobot for example just hangs down with random actions)

Can do replanning in domains that are non-static

Multi-agent path planning is poly-time (non-optimal) in discrete domains

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

They may get a BAXTER(!)

Minimax regret: Savage ’51, Niehas ’48

Good for human interaction, because minimax results agree more with human intuition than game-theoretic results