In this paper, we are considering advanced pathplanning problems that feature finding paths for multiple units subject to rich path constraints. Examples of richer constraints are the following of other units or to stay out of sight of a specific unit. Little attention has so far been given to richer pathplanning problem where the objective is more than reaching a specific destination from a starting point such that the path length is minimized. Richer pathplanning problems occur in many complex real-world scenarios, ranging from computer games to military movement planning. In this paper, a novel way to formally specify such problems and a new local-search strategy to solve such problems are proposed and demonstrated by a prototype implementation. Among the design goals are real-time computability as well as extendibility for new constraints and search heuristics.