One of big challenges in robotics research is in enabling robot navigation in crowded environments. As one key technical difficulty, in such environment, a robot would trap into a deadlock state where the robot is unable to advance to its destination, especially when it is surrounded by pedestrians and perceives them as obstacles which the robot is programmed to avoid collision against. This problem is widely known as a "freezing robot problem" and acts as a major hurdle in deploying robotic systems in real-world applications. We study this problem in the context of human-robot interaction and develop new algorithms that ensure deadlock-free robot navigation in pedestrian-populated environments. The project aims at developing both principles and algorithms to address the freezing robot problem: we begin by investigating how the human-robot interaction can be understood as a feedback interconnection of human and robot decision-making models and then identify under what specifications on the robot's decision-making model, the robot is guaranteed to be deadlock-free. We will explore tools from feedback control theory and game theory to find such specifications and develop robot navigation algorithms satisfying them. Ultimately, we will carrying out experiments using multiple mobile robot platforms to validate our framework in pedestrian-populated areas.