Back to results
US 12,572,153 B1Granted
Route planning for aerial vehicles in indoor spaces
AssigneeAmazon Technologies, Inc.
InventorsKah Kuen Fu, Chen Hu, Chong Huang, Yang Liu
Life of this patent
Estimating the term…
Abstract
An aerial vehicle configured for operating within an indoor space is carried through the indoor space by a user, and data regarding positions and orientations of the aerial vehicle at each of a plurality of points is used to generate a route for the aerial vehicle. The route is simplified according to an iterative fit algorithm, and levels of collision risk are calculated for each of the points of the simplified route based on distances between segments of the simplified route leading into or from such points and obstacles or other objects. Points having unacceptable levels of collision risk are relocated, as necessary.
Claims20
A method comprising:
- receiving first data representing a first route for a first aerial vehicle within an indoor space, wherein the first data indicates a first plurality of points in three-dimensional space, and wherein the first route begins at a first point of the first plurality of points and ends at a second point of the first plurality of points;
- determining a second route for the first aerial vehicle based on the first data and a first threshold distance, wherein the second route comprises a first subset of the first plurality of points defining a first plurality of segments, and wherein each point of the first plurality of points is within the first threshold distance of at least one of the first plurality of segments;
- receiving second data indicating positions of a plurality of objects within the indoor space, wherein the second data was captured by at least one sensor provided aboard one of the first aerial vehicle or a second aerial vehicle;
- calculating a risk of collision for each one of the first subset of the first plurality of points, wherein the risk of collision calculated for each one of the first subset of the first plurality of points is calculated based at least in part on a minimum distance between each one of the first plurality of segments into or out of the one of the first subset of the first plurality of points and a nearest one of the plurality of objects;
- determining that a risk of collision calculated for a third point of the first plurality of points exceeds a predetermined threshold, wherein a first segment of the first plurality of segments extends between the third point and a fourth point of the first plurality of points, and wherein a second segment of the first plurality of segments extends between the third point and a fifth point of the first plurality of points;
- and
- in response to determining that the risk of collision calculated for the third point of the first plurality of points exceeds the predetermined threshold, selecting a sixth point in three-dimensional space, wherein the sixth point is proximate the third point;
- determining that a third segment defined between the sixth point and the fourth point is not within a second threshold distance from the nearest one of the plurality of objects;
- determining that a fourth segment defined between the sixth point and the fifth point is not within the second threshold distance from the nearest one of the plurality of objects;
- determining a third route for the first aerial vehicle, wherein the third route comprises a second plurality of points in three-dimensional space defining a second plurality of segments, wherein the second plurality of points comprises the first point, the fourth point, the fifth point, and the sixth point, wherein the second plurality of points does not comprise the third point, and wherein the second plurality of segments comprises the third segment and the fourth segment;
- and
- programming the first aerial vehicle to travel along the third route.
9 more elements
An aerial vehicle comprising:
- a plurality of propulsion motors;
- at least one sensor, wherein the at least one sensor comprises an inertial sensor, a position sensor, or an imaging device;
- a control system in communication with each of the plurality of propulsion motors and the at least one sensor, wherein the control system comprises one or more computer processors and one or more memory components, and
- wherein the one or more memory components are programmed with one or more sets of instructions that, when executed by the one or more computer processors, cause the aerial vehicle to at least:
- receive first data representing a first route within an indoor space, wherein the first data indicates a first plurality of points in three-dimensional space, and wherein the first route begins at a first point of the first plurality of points and ends at a second point of the first plurality of points;
- determine a second route based on the first data and a first threshold distance, wherein the second route comprises a first subset of the first plurality of points defining a first plurality of segments, and wherein each point of the first plurality of points is within the first threshold distance of at least one of the first plurality of segments;
- receive second data indicating positions of a plurality of objects within the indoor space, wherein the second data was captured by the at least one sensor;
- calculate a risk of collision for each one of the first subset of the first plurality of points, wherein the risk of collision calculated for each one of the first subset of the first plurality of points is calculated based at least in part on a minimum distance between each one of the first plurality of segments into or out of the one of the first subset of the first plurality of points and a nearest one of the plurality of objects;
- determine that a risk of collision calculated for a third point of the first plurality of points exceeds a predetermined threshold, wherein a first segment of the first plurality of segments extends between the third point and a fourth point of the first plurality of points, and wherein a second segment of the first plurality of segments extends between the third point and a fifth point of the first plurality of points;
- and
- in response to determining that the risk of collision calculated for the third point of the first plurality of points exceeds the predetermined threshold,
- select a sixth point in three-dimensional space, wherein the sixth point is proximate the third point;
- determine that a third segment defined between the sixth point and the fourth point is not within a second threshold distance from the nearest one of the plurality of objects;
- determine that a fourth segment defined between the sixth point and the fifth point is not within the second threshold distance from the nearest one of the plurality of objects;
- determine a third route for the aerial vehicle, wherein the third route comprises a second plurality of points in three-dimensional space defining a second plurality of segments, wherein the second plurality of points comprises the first point, the fourth point, the fifth point, and the sixth point, wherein the second plurality of points does not comprise the third point, and wherein the second plurality of segments comprises the third segment and the fourth segment;
- and
- program the aerial vehicle to travel along the third route.
14 more elements
A computer system comprising:
- a plurality of computer processors;
- at least one data store;
- and
- at least one transceiver,
- wherein the at least one data store is programmed with one or more sets of instructions that, when executed by the computer system, cause the computer system to at least:
- receive first data representing a first route for a first aerial vehicle within an indoor space, wherein the first data indicates a first plurality of points in three-dimensional space, and wherein the first route begins at a first point of the first plurality of points and ends at a second point of the first plurality of points;
- determine a second route for the first aerial vehicle based on the first data and a first threshold distance, wherein the second route comprises a first subset of the first plurality of points defining a first plurality of segments, and wherein each point of the first plurality of points is within the first threshold distance of at least one of the first plurality of segments;
- receive second data indicating positions of a plurality of objects within the indoor space, wherein the second data was captured by at least one sensor provided aboard one of the first aerial vehicle or a second aerial vehicle;
- calculate a risk of collision for each one of the first subset of the first plurality of points, wherein the risk of collision calculated for each one of the first subset of the first plurality of points is calculated based at least in part on a minimum distance between each one of the first plurality of segments into or out of the one of the first subset of the first plurality of points and a nearest one of the plurality of objects;
- determine that a risk of collision calculated for a third point of the first plurality of points exceeds a predetermined threshold, wherein a first segment of the first plurality of segments extends between the third point and a fourth point of the first plurality of points, and wherein a second segment of the first plurality of segments extends between the third point and a fifth point of the first plurality of points;
- and
- in response to determining that the risk of collision calculated for the third point of the first plurality of points exceeds the predetermined threshold,
- select a sixth point in three-dimensional space, wherein the sixth point is proximate the third point;
- determine that a third segment defined between the sixth point and the fourth point is not within a second threshold distance from the nearest one of the plurality of objects;
- determine that a fourth segment defined between the sixth point and the fifth point is not within the second threshold distance from the nearest one of the plurality of objects;
- determine a third route for the first aerial vehicle, wherein the third route comprises a second plurality of points in three-dimensional space defining a second plurality of segments, wherein the second plurality of points comprises the first point, the fourth point, the fifth point, and the sixth point, wherein the second plurality of points does not comprise the third point, and wherein the second plurality of segments comprises the third segment and the fourth segment;
- and
- program the first aerial vehicle to travel along the third route.
15 more elements
Dependencies are inferred from the claim text.