Abstract:
Path planning aims at navigating a robot from an initial configuration to a goal configuration without violating various constraints. The problem of path planning is theoretically intractable (PSPACE hard), but in everyday life we (as human beings) navigate in our environment without much difficulty. This is partially due to the experiences we learned since childhood. The learning process may be complex, but one of the reasons that we can learn such tasks is that most objects we encounter today are similar or identical to the objects we encountered yesterday or even years ago. Environments with similar objects are quite common. For example, desks and chairs in a classroom or in an office may be moved around from one place to another frequently, but unfamiliar items are seldom introduced. Even different environments, such as two apartments, or a manufacturing factory and an airport garage, may share many similar items. The main differences are usually in the arrangements. Similar environments can also be found in simulated reality, e.g., in different levels of a video game or in the different regions of a virtual reality world, where many objects are intentionally duplicated to reduce the (e.g., modeling and rendering) complexity. A dynamic environment where obstacles allowed to move can be considered as a continuous sequence of similar static environments due to motion coherence. We term "discrete similar-workspace problem" for static environments and "continuous similar-workspace problem" for dynamic environments. In this thesis, I investigated path planners that can address both problems and recognize this similarity in order to significantly improve efficiency and completeness.
