Path-Planning Algorithm for a Wheeled Robot Crossing a Room Around Fixed Obstacles

Design an algorithm that gets a robot from a starting point A to a destination point B inside a room, and walk through it step by step. The setting: - The room is rectilinear: every wall runs along one of two perpendicular directions, so the floor plan is a rectangle or a shape made of right-angled corners, such as an L. - Obstacles stand in the room. They are fixed: the robot cannot push them aside, reshape them or drive across them. - The robot rolls on wheels and has to stay on the floor the whole time, so climbing over an obstacle or passing above it is not an option. Explain how the robot should represent the room, how it chooses a route from A to B, and how it then follows that route. Pseudocode or a precise step-by-step description is fine. ```hint Make the floor searchable Think about how to describe the floor so that "places the robot could be" and "moves between them" become something a program can explore systematically, and remember that the robot itself takes up space. ``` ### Clarifying Questions - Does the robot have a map of the walls and obstacles before it starts, or must it discover obstacles with its sensors while it drives? - Should the route be the shortest, the quickest (if turning or stopping costs time), or any route that arrives without a collision? - Can the robot drive at any angle or only parallel to the walls, and can it turn on the spot or does it steer like a car with a minimum turning radius? - How wide is the robot compared with the gaps between obstacles, and what should it do if no gap lets it reach B? ### What a Strong Answer Covers - A model of the room and its obstacles that accounts for the robot's physical size. - A search method that finds a route whenever one exists, recognizes when none does, and has a stated cost in time and memory. - Turning the planned route into wheel commands, and coping with position drift or a map that proves wrong. - Edge cases such as an unreachable destination, a gap narrower than the robot, and A equal to B. - Trade-offs such as map resolution, shortest route versus fewest turns, and planning ahead versus sensing on the way, explained so a non-specialist can follow. ### Follow-up Questions - A person steps into the robot's path halfway along the route. How does your algorithm respond? - Each turn takes the robot much longer than driving one cell straight. How would you change the planner to favor routes with fewer turns? - The room becomes a warehouse floor with thousands of obstacles. How do you keep planning fast enough?