# Fire Fighting robot searching for fire in arena algorithm

i am working on a firefighting robot and i am struggling to find a way to search all rooms in an arena like this

i thought of using the Wall follower rule but it will miss a room , if i am understanding it correctly.

Wall following is a good local strategy, but as you point out it might miss a room because it does not consider the global map. Your problem could be cast as a simultaneous localization and mapping problem (SLAM), where the robot builds a map while it travels around. This way, it can track where it has/has not been and find rooms it missed earlier.

In 2D, you would represent the map using an occupancy grid, which assigns values (occupied, unknown, free) to small squares of space. There many algorithms for handling how to use sensor data to estimate which cells are free/occupied - let's ignore that for now.

Assuming you have perfect knowledge of where you are and what you are seeing, then your grid cells will be in one of three states: occupied, unknown and free. A simple but effective strategy for exploring a room is called next-best view planning, where the robot travels to the location where it thinks it will see the most. This depends on a sensor model (e.g. "can see 5 cells away in all directions but not through walls"), and a model of the room (e.g. "assume straight walls continue going straight"). This planner is greedy, so you will want to enforce some common sense rules to keep it from going to the other side of the room unless there's nothing left where it is.

This is a fundamental problem for roboticists, and there are quite a few packages out there for solving the exploration problem. This ROS package looks like a good starting place (or this one).

According to the given map, the robot is the circle and the goals are the crosses. To move to every room a path must be generated first. The path, the robot will travel, is a subgraph of a navmesh. A navmesh consists of possible waypoints which can be visited without bouncing to an obstacle. The most dominant algorithm for finding a navmesh and a path for the robot is the Rapidly-exploring random tree algorithm. A simple version can be found on the homepage of Steve LaValle RRT python. For implmenting a more sophisticated pathplanner which copes with the obstacles the paradigma of objectorientied programming is a good practice. The idea is to use one or more classes for building the obstacle detection, find the shortest path, extend the RRT tree and perhaps visualize the graph in the map.

As inspiration please visit the UML Chart on page 42, Morten Strandberg: Robot Path Planning: An Object-Oriented Approach, 2004 Thats not a class diagram for a firefighting robot, but gives an impression that building a path planner is done with different classes, which are combined together to a more complex system.

• does RRT needs to know the arena before hand?? , sorry if i was unclear the robot doesn't know anything about the arena when it starts . – tom fox Sep 1 '17 at 11:26
• and also the robot doesn't know the position of the rooms , all he knows that when he enters a room , @Manuel – tom fox Sep 1 '17 at 14:25
• RRT typically requires a known graph. Your robot sees at least a part of the environment and can use RRT on that piece though. I tried to focus more on the question of where to go in the answer I posted. Also, I don't think object oriented programming is particularly relevant - it's not quite the same thing as saying the code is modular. – combo Sep 1 '17 at 16:26