Q-Link: A general planning architecture for navigation with qualitative relational information

Qualitative relational maps (QRM) are useful environmental representations for robots that incorporate information about point like and extended landmarks. While several methods for generating QRM exist, no general planning methods for QRM are available. This paper introduces qualitative linking (Q-Link), a general three level planning architecture for use with any type of QRM. Q-Link generates high level plans over 'links' in a QRM and uses local planners to execute trajectories to enable a robot to navigate from a start to a goal. Q-Link is adaptable to any robotic platform, and can plan over deterministic information from a QRM or uncertain information from a probabilistic QRM. Path completion guarantees and distance bounds are provided for environments with point landmarks and no occlusions. The performance of Q-Link is tested in simulation and an in vivo study, where path completion is not guaranteed. The simulation studies show that Q-Link is robust to failure in scenarios where a specific landmark density is guaranteed with minimal occlusions (over 97% path completion rate), but sensitive to environments with insufficient landmark density (up to 74% failure rate) . The in vivo studies show that Q-Link is robust to failure in an outdoor navigation scenario for three different environment types that contain point landmarks and extended landmarks (72% path completion rate).