Travel path identification based upon statistical relationships between path costs
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G01C-021/00
G08G-005/00
G08G-001/0968
G06Q-010/04
G01C-021/20
G01C-021/34
출원번호
US-0324861
(2014-07-07)
등록번호
US-9714831
(2017-07-25)
발명자
/ 주소
Kapoor, Ashish
Dey, Debadeepta
Kolobov, Andrey
Eden, Semiha Ece Kamar
Caruana, Richard
Horvitz, Eric
출원인 / 주소
Microsoft Technology Licensing, LLC
대리인 / 주소
Medley, Behrens & Lewis, LLC
인용정보
피인용 횟수 :
4인용 특허 :
2
초록▼
Various technologies pertaining to dynamically identifying travel segments to be taken by a traveler traveling in a region are described herein, where observations about travel segments in the region are sparse and subject to alteration. A computer-implemented graph can be loaded into a memory, wher
Various technologies pertaining to dynamically identifying travel segments to be taken by a traveler traveling in a region are described herein, where observations about travel segments in the region are sparse and subject to alteration. A computer-implemented graph can be loaded into a memory, where the computer-implemented graph is representative of the region. The computer-implemented graph includes nodes that represent locations in the region and edges that represent travel segments of the region, where the edges have costs assigned thereto, and further where there is a defined statistical relationship between the costs. When an observation about a travel path is received, using the computer-implemented graph, inferences can be made about costs of traversing other travel paths in the region.
대표청구항▼
1. A method executed by a processor of a computing device, the method comprising: receiving a computer-implemented graph that comprises nodes and edges, the computer-implemented graph representative of a region over which a machine is able to travel, the nodes representative of respective locations
1. A method executed by a processor of a computing device, the method comprising: receiving a computer-implemented graph that comprises nodes and edges, the computer-implemented graph representative of a region over which a machine is able to travel, the nodes representative of respective locations in the region, the edges representative of travel segments between locations, wherein each edge in the edges connects a respective pair of nodes in the nodes, each node in the nodes connected to at least one other node by a respective edge in the edges, the edges have respective distributions over costs assigned thereto, and the respective costs have a statistical relationship therebetween;receiving data from a sensor, the data being about a travel segment in the travel segments;responsive to receiving the data, updating the respective distributions over the costs of the edges in the computer-implemented graph based upon the data and the statistical relationship;identifying a particular travel segment in the travel segments over which the machine is to travel, the identifying based upon the updating of the respective distributions over the costs of the edges and a destination location of the machine; andresponsive to identifying the particular travel segment, directing the machine to travel along the particular travel segment in the travel segments, wherein directing the machine to travel along the particular travel segment comprises outputting a signal that causes the machine to travel along the particular travel segment in the travel segments. 2. The method of claim 1, wherein the machine comprises the processor. 3. The method of claim 2, wherein the respective distributions over the costs of the edges are updated in the computer-implemented graph as the machine travels in the region. 4. The method of claim 1, the machine being one of an airplane, a water vessel, a spacecraft, a drone, a robot, or an automobile. 5. The method of claim 1, the machine comprises the sensor. 6. The method of claim 1, another machine in the region comprises the sensor. 7. The method of claim 1, the statistical relationship being a joint probability distribution over the costs. 8. The method of claim 7, the joint probability distribution being a Gaussian distribution. 9. The method of claim 7, wherein identifying the particular travel segment in the travel segments over which the machine is to travel comprises: sampling from the joint probability distribution to acquire respective discrete cost values for the edges;identifying, from amongst possible travel routes from a current location of the machine to the destination location, a travel route that has a lowest aggregate cost from amongst the possible travel routes, the travel route being over multiple travel segments; andidentifying the particular travel segment based upon the identifying of the travel route, wherein the particular travel segment is a first travel segment in the travel route that begins at the current location of the machine. 10. The method of claim 9, wherein identifying the particular travel segment in the travel segments over which the machine is to travel further comprises: sampling from the joint probability distribution multiple times to acquire multiple discrete cost values for each edge in the edges;for each edge in the edges, computing a respective average cost value; andidentifying the travel route based upon respective average cost values for the edges. 11. The method of claim 1, further comprising repeating the acts of: receiving data from the sensor;updating the respective costs of the edges;identifying a particular travel segment in the travel segments; andoutputting a signal that directs the machine to travel along the particular travel segment in the travel segments until the machine reaches the destination location. 12. The method of claim 1, the statistical relationship is a function of time. 13. A computing system comprising: a processor; andmemory that stores instructions that, when executed by the processor, cause the processor to perform acts comprising: receiving a computer-implemented graph that comprises nodes and edges, the computer-implemented graph representative of a region over which a machine is able to travel, the nodes representative of respective locations in the region, the edges representative of travel segments between locations, wherein each edge in the edges connects a respective pair of nodes in the nodes, each node in the nodes connected to at least one other node by a respective edge in the edges, the edges have respective distributions over costs assigned thereto, and the respective costs have a statistical relationship therebetween;receiving data from a sensor, the data being about a travel segment in the travel segments;responsive to receiving the data, updating the respective distributions over the costs of the edges in the computer-implemented graph based upon the data and the statistical relationship;identifying a particular travel segment in the travel segments over which the machine is to travel, the identifying based upon the updating of the respective distributions over the costs of the edges and a destination location of the machine; andresponsive to identifying the particular travel segment, directing the machine to travel along the particular travel segment in the travel segments, wherein directing the machine to travel along the particular travel segment comprises outputting a signal that causes the machine to travel along the particular travel segment in the travel segments. 14. The computing system of claim 13, the machine being one of an airplane, a water vessel, a spacecraft, a drone, a robot, or an automobile. 15. The computing system of claim 13, the machine comprises the sensor. 16. The computing system of claim 13, another machine in the region comprises the sensor. 17. The computing system of claim 13, the statistical relationship being a joint probability distribution over the costs. 18. The computing system of claim 17, the joint probability distribution being a Gaussian distribution. 19. The computing system of claim 18, wherein identifying the particular travel segment in the travel segments over which the machine is to travel comprises: sampling from the joint probability distribution to acquire respective discrete cost values for the edges;identifying, from amongst possible travel routes from a current location of the machine to the destination location, a travel route that has a lowest aggregate cost from amongst the possible travel routes, the travel route being over multiple travel segments; andidentifying the particular travel segment based upon the identifying of the travel route, wherein the particular travel segment is a first travel segment in the travel route that begins at the current location of the machine. 20. A computer-readable storage medium comprising instructions that, when executed by a processor, cause the processor to perform acts comprising: receiving a computer-implemented graph that comprises nodes and edges, the computer-implemented graph representative of a region over which a machine is able to travel, the nodes representative of respective locations in the region, the edges representative of travel segments between locations, wherein each edge in the edges connects a respective pair of nodes in the nodes, each node in the nodes connected to at least one other node by a respective edge in the edges, the edges have respective distributions over costs assigned thereto, and the respective costs have a statistical relationship therebetween;receiving data from a sensor, the data being about a travel segment in the travel segments;responsive to receiving the data, updating the respective distributions over the costs of the edges in the computer-implemented graph based upon the data and the statistical relationship;identifying a particular travel segment in the travel segments over which the machine is to travel, the identifying based upon the updating of the respective distributions over the costs of the edges and a destination location of the machine; andresponsive to identifying the particular travel segment, directing the machine to travel along the particular travel segment in the travel segments, wherein directing the machine to travel along the particular travel segment comprises outputting a signal that causes the machine to travel along the particular travel segment in the travel segments.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (2)
Ingvalson, Ryan, Shared state selection and data exchange for collaborative navigation using conditionally independent parallel filters.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.