should do a lawnmower pattern (uniform coverage) and on each obstacle boundary, spawn a boundary explorer.
The boundary explorer would try to move a small distance forward, if it could, it would back up, and turn right a small amount. Then it would try moving forward again, looking for the most right it could turn whilst still being able to walk forwards. This would trace the boundary clockwise.
If the lawnmower grid resolution pattern was half the smallest diameter of an obstacle. You would be guaranteed to discover the topology of the map (assuming the map walk operator is bidirectional, which it isn't, but should be.)
This is called a boustrophedon decomposition[1] (the name comes from the movement an ox makes when plowing a field). It's used for minesweeping robots among other things. Constructing the decomposition simultaneously covers the space being explored, so a robot can explore and mow grass at the same time. Applied as a coverage algorithm, it's much more efficient than a random walk.
The robot is usually modelled as having a non-zero footprint since coverage is often a goal, but a radius of zero can be used for exploration. To explore a space with minimum obstacle radius R and robot radius r, each sweep can be 2(R+r) units wide.
oh true. So there will also be another type of boundary which has a direction associated. And a sorta don't know area when you are mid fall with some limited manoeuvrability (non-holonomic movement). Best not to try and categorise the non-holonomic areas in too much detail as that's a rabbit hole.
should do a roomba pattern. random coverage, and guarantee to get stuck in a inverted polygon face as soon as you leave the room thinking the build will still for an hour.
The boundary explorer would try to move a small distance forward, if it could, it would back up, and turn right a small amount. Then it would try moving forward again, looking for the most right it could turn whilst still being able to walk forwards. This would trace the boundary clockwise.
If the lawnmower grid resolution pattern was half the smallest diameter of an obstacle. You would be guaranteed to discover the topology of the map (assuming the map walk operator is bidirectional, which it isn't, but should be.)