Generation of navigational paths using recursive partitioning of unoccupied space

A computing device, comprising:

• a memory;
• and
• a processor communicatively coupled with the memory, the processor configured to:
• obtain a map of a facility, the map containing at least one obstacle and unoccupied space;
• partition the unoccupied space into a set of initial cells, each initial cell having an initial boundary containing a portion of the unoccupied space according to proximity between the portion of the unoccupied space and the at least one obstacle;
• generate an intermediate map containing (i) the at least one obstacle, (ii) a set of virtual obstacles on the initial boundaries, and (iii) remaining unoccupied space;
• partition the remaining unoccupied space into a set of updated cells, each updated cell having an updated boundary containing a portion of the remaining unoccupied space according to proximity between the portion of the remaining unoccupied space, the at least one obstacle, and the virtual obstacles;
• and
• provide the set of updated cells to a navigational controller for generation of a navigational path for a mobile apparatus, the navigational path formed by segments of the updated boundaries,
• wherein the processor is configured to generate the intermediate map by:
• generating candidate virtual obstacles on the initial boundaries;
• and
• retaining a subset of the candidate virtual obstacles as the virtual obstacles by determining whether each candidate virtual obstacle is surrounded by unoccupied space having a predetermined threshold radius.

A non-transitory computer-readable medium storing computer-readable instructions executable by a processor to:

• obtain a map of a facility, the map containing at least one obstacle and unoccupied space;
• partition the unoccupied space into a set of initial cells, each initial cell having an initial boundary containing a portion of the unoccupied space according to proximity between the portion of the unoccupied space and the at least one obstacle;
• generate an intermediate map containing (i) the at least one obstacle, (ii) a set of virtual obstacles on the initial boundaries, and (iii) remaining unoccupied space;
• partition the remaining unoccupied space into a set of updated cells, each updated cell having an updated boundary containing a portion of the remaining unoccupied space according to proximity between the portion of the remaining unoccupied space, the at least one obstacle, and the virtual obstacles;
• and
• provide the set of updated cells to a navigational controller for generation of a navigational path for a mobile apparatus, the navigational path formed by segments of the updated boundaries,
• wherein the instructions, when executed, cause the processor to generate the intermediate map by:
• generating candidate virtual obstacles on the initial boundaries;
• and
• retaining a subset of the candidate virtual obstacles as the virtual obstacles by determining whether each candidate virtual obstacle is surrounded by unoccupied space having a predetermined threshold radius.