Generation of Navigational Paths Using Recursive Partitioning of Unoccupied Space
A method includes: obtaining a facility map containing at least one obstacle and unoccupied space; partitioning 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 a proximity between the portion of the unoccupied space and the at least one obstacle; generating an intermediate map containing the at least one obstacle, a set of virtual obstacles on the initial boundaries, and remaining unoccupied space; partitioning 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 providing 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.
1 . A method, comprising:
obtaining a map of a facility, the map containing at least one obstacle and unoccupied space;
partitioning 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;
generating 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;
partitioning 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 a proximity between the portion of the remaining unoccupied space, the at least one obstacle, and the virtual obstacles; and
providing 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.
2 . The method of claim 1 , further comprising:
obtaining, at the navigational controller, an origin location and a target location in the facility;
generating a path between the origin location and the target location based on the updated cells, the path comprising segments of the updated boundaries; and
controlling the mobile apparatus to navigate along the path.
3 . The method of claim 1 , wherein the initial cells and the updated cells are Voronoi cells.
4 . The method of claim 1 , wherein the virtual obstacles are single-point obstacles.
5 . The method of claim 1 , wherein generating the intermediate map includes:
generating candidate virtual obstacles on the initial boundaries; and
retaining a subset of the candidate virtual obstacles as the virtual obstacles.
6 . The method of claim 5 , further comprising generating the candidate virtual obstacles with a predetermined separation distance.
7 . The method of claim 5 , wherein retaining the subset of the candidate virtual obstacles includes determining whether each candidate virtual obstacle is surrounded by unoccupied space having a predetermined threshold radius.
8 . The method of claim 7 , wherein the threshold radius is based on a dimension of the mobile apparatus.
9 . The method of claim 1 , further comprising, prior to providing the set of updated cells:
generating a further intermediate map containing (i) the at least one obstacle, (ii) a further set of virtual obstacles on the updated boundaries, and (iii) further remaining unoccupied space; and
partitioning the further remaining unoccupied space into a set of further updated cells.
10 . 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.
11 . The computing device of claim 10 , wherein the processor is further configured to:
obtain, at the navigational controller, an origin location and a target location in the facility;
generate a path between the origin location and the target location based on the updated cells, the path comprising segments of the updated boundaries; and
control the mobile apparatus to navigate along the path.
12 . The computing device of claim 10 , wherein the initial cells and the updated cells are Voronoi cells.
13 . The computing device of claim 10 , wherein the virtual obstacles are single-point obstacles.
14 . The computing device of claim 10 , 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.
15 . The computing device of claim 14 , wherein the processor is further configured to generate the candidate virtual obstacles with a predetermined separation distance.
16 . The computing device of claim 14 , wherein the processor is configured to retain the subset of the candidate virtual obstacles by determining whether each candidate virtual obstacle is surrounded by unoccupied space having a predetermined threshold radius.
17 . The computing device of claim 16 , wherein the threshold radius is based on a dimension of the mobile apparatus.
18 . The computing device of claim 1 , wherein the processor is further configured, prior to providing the set of updated cells, to:
generate a further intermediate map containing (i) the at least one obstacle, (ii) a further set of virtual obstacles on the updated boundaries, and (iii) further remaining unoccupied space; and
partition the further remaining unoccupied space into a set of further updated cells.
19 . 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.