We study motion planning problems, finding trajectories connecting two configurations, from two different perspectives: optimality and survivability.  For the problem of finding optimal trajectories, we provide a model such that the existence of optimal trajectories is guaranteed, and design an algorithm to find approximately optimal trajectories for a kinematic planar robot within this model.

We also design an algorithm to build data structures to represent the configuration space, supporting optimal trajectory queries for any given pair of configurations in an obstructed environment.

We are also interested in planning paths for expendable robots moving in a threat environment. Since robots are expendable, our goal is to ensure certain amount of robots reaching the goal.  We consider a new motion planning problem, maximum k-survivability: given two points in a stochastic threat environment, find n paths connecting two given points while maximizing the probability that at least k paths reach the goal.

Intuitively, a good solution should be diverse to avoid several paths being blocked simultaneously, and paths should be short so that robots can quickly pass through dangerous areas.  Finding sets of paths with maximum k-survivability is NP-hard.  We design two algorithms: a complete algorithm that finds an optimal list of paths, and a heuristic method that finds paths with high k-survivability.