IP Library Granted Patent US 12,601,600
Granted Patent B2
US 12,601,600 · App. 18/242,360 · Granted Apr 14, 2026

Interpreting and resolving map-related queries using a language model

Inventors: Dragomir Dimitrov Yankov (Palo Alto, CA); Chiqun Zhang (Sunnyvale, CA); Antonios Karatzoglou (San Francisco, CA); Helen Alta Craig (Palo Alto, CA)
Assignee: Microsoft Technology Licensing, LLC
G01C21/3407G06F16/24545G06F16/2462G06F16/284G06F16/29G06F16/3329G06F40/237G06F40/284G06F40/295G06F40/30G06F40/35G06F40/40G06N3/042G06N3/045G06N20/00
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,601,600
App. No.
18/242,360
Granted
Apr 14, 2026
Kind
B2
Abstract

A technique for interacting with map-related information integrates the use of a machine-trained language model. Upon submission of a query, the technique uses the machine-trained language model to assess at least one intent associated with the query. The technique then invokes an intent-specific processing flow to provide an output result. Each processing flow invokes the use of at least one processing engine to perform an engine-specific task, such as geocoding, route finding, or image retrieval. A processing flow can also call on the machine-trained language model one or more additional times. In some cases, the technique includes a feedback mechanism for soliciting additional information from a user.

Claims (54)

1 . A method for processing a query that relates to a map using a control computer program that orchestrates functions performed by a computing system, comprising:

receiving the query;

generating a prompt to submit to a machine-trained language model, the prompt including a series of tokens, the prompt expressing the query and describing a task that the machine-trained language model is being asked to perform;

sending the prompt to the machine-trained language model;

receiving a response generated by the machine-trained language model based on the prompt, the response identifying one or more intents of a predetermined set of intents that are relevant to the query; and

in a multiplexing operation, invoking a particular processing pipeline based on the one or more intents identified by the machine-trained model, wherein the particular processing pipeline is one of plural context-specific processing pipelines executed by the control computer program,

wherein at least one context-specific processing pipeline of the plural context-specific pipelines calls the machine-trained language model to classify each of two or more entities specified by the query as a primary entity or a secondary entity, wherein the primary entity has a higher priority than the secondary entity, indicating that the machine-trained language model is to treat the primary entity as an anchor, and then select the secondary entity from among entities that are located near the primary entity,

wherein at least one context-specific processing pipeline of the plural context-specific pipelines includes: identifying, using a routing engine of a multi-engine system, one or more proposed routes based on the query; and validating each proposed route by determining whether the proposed route has a spatial distribution of locations that satisfies a prescribed test, and/or determining whether the proposed route has a travel time that is within a prescribed temporal deviation from a reference travel time, and

wherein at least one context-specific processing pipeline of the plural context-specific pipelines generates an interactive map pertaining to the query, and presents an image that has been retrieved in prescribed proximity to the interactive map.

2 . The method of claim 1 , further comprising generating a seed prompt that describes a particular task to be performed by the machine-trained language model, and sending the seed prompt to the machine-trained language model, the seed prompt also specifying a particular output format to be used by the machine-trained language model to present results of processing performed by the machine-trained language model.

3 . The method of claim 1 , wherein the query refers to a particular entity by describing a class associated with the particular entity, there being two or more specific entities in the class having different respective locations, and wherein the machine-trained language model is instructed to interpret the particular entity as a secondary entity.

4 . The method of claim 1 ,

wherein the query is submitted in a dialogue session having a dialogue history,

wherein the method further comprises calling the machine-trained language model to augment the query with information extracted from the dialog history, to produce an augmented query, and

wherein the method further comprises submitting the augmented query to machine-trained language model.

5 . The method of claim 1 , wherein the method further comprises generating an output message using the machine-trained language model that conveys a request to supply another query that provides additional information, beyond information that is imparted by the query that is originally received.

6 . The method of claim 1 , wherein the computer control program further includes calling the machine-trained language model to determine an order in which entities referenced by the query are to be connected, or to indicate that an order does not apply to the entities referenced by the query.

7 . The method of claim 1 , wherein the the computer control program determines a location associated with a particular entity referenced by the query by calling a geocoding engine of the multi-engine system.

8 . The method of claim 1 , wherein the computer control program identifies a particular entity referenced by the query on a basis of the query and/or an answer to the query generated by the machine-trained language model.

9 . The method of claim 1 ,

wherein the one or more intents include a route-finding intent that expresses a request to find a route over a physical space,

wherein the control computer program further includes:

determining a location associated with each entity referenced by the query a geocoding engine of the multi-engine system; and

identifying the one or more proposed routes based on an output result of the geocoding engine.

10 . The method of claim 1 ,

wherein the one or more intents include a travel intent or an atlas intent that expresses an intent to retrieve an image, and

wherein the computer control program includes retrieving the image from a data store that pertains to a topic expressed by the query.

11 . A computing system for processing a query that relates to a map, comprising:

an instruction data store for storing computer-readable instructions, the computer-readable instructions providing a control computer program that orchestrates functions performed by the computing system; and

a processing system for executing the computer-readable instructions in the data store, to perform operations including:

receiving the query;

generating a prompt to submit to a machine-trained language model, the prompt including a series of tokens, the prompt expressing the query and describing a task that the machine-trained language model is being asked to perform;

sending the prompt to the machine-trained language model;

receiving a response generated by the machine-trained language model based on the prompt, the response identifying one or more intents of a predetermined set of intents that are relevant to the query; and

in a multiplexing operation, invoking a particular processing pipeline based on the one or more intents identified by the machine-trained model, wherein the particular processing pipeline is one of plural context-specific processing pipelines executed by the control computer program,

wherein at least one context-specific processing pipeline of the plural context-specific pipelines calls the machine-trained language model to classify each of two or more entities specified by the query as a primary entity or a secondary entity, wherein the primary entity has a higher priority than the secondary entity, indicating that the machine-trained language model is to treat the primary entity as an anchor, and then select the secondary entity from among entities that are located near the primary entity,

wherein at least one context-specific processing pipeline of the plural context-specific pipelines includes: identifying, using a routing engine of a multi-engine system, one or more proposed routes based on the query; and validating each proposed route by determining whether the proposed route has a spatial distribution of locations that satisfies a prescribed test, and/or determining whether the proposed route has a travel time that is within a prescribed temporal deviation from a reference travel time, and

wherein at least one context-specific processing pipeline of the plural context-specific pipelines generates an interactive map pertaining to the query, and presents an image that has been retrieved in prescribed proximity to the interactive map.

12 . The computing system of claim 11 , wherein the computer control program identifies a particular entity referenced by the query on a basis of the query and/or the an answer to the query generated by the machine-trained language model.

13 . The computing system of claim 11 ,

wherein the one or more intents generated by the machine-trained language model include a route-finding intent that expresses a request to find a route over a physical space,

wherein the control computer program further includes:

determining a location associated with each entity referenced by the query using a geocoding engine of the multi-engine system; and

identifying the one or more proposed routes based on an output result of the geocoding engine.

14 . The computing system of claim 11 , wherein the one or more intents include a travel intent that expresses an intent to retrieve a travel-related image that provides assistance when traveling in a particular region, or an atlas intent that conveys scientific, historical, and/or news-related information about the particular region.

15 . A computer-readable storage medium for storing computer-readable instructions, a processing system executing the computer-readable instructions to perform operations, the operations comprising:

receiving the query;

generating a prompt to submit to a machine-trained language model, the prompt including a series of tokens, the prompt expressing the query and describing a task that the machine-trained language model is being asked to perform;

sending the prompt to the machine-trained language model;

receiving a response generated by the machine-trained language model based on the prompt, the response identifying one or more intents of a predetermined set of intents that are relevant to the query; and

in a multiplexing operation, invoking a particular processing pipeline based on the one or more intents identified by the machine-trained model, wherein the particular processing pipeline is one of plural context-specific processing pipelines executed by the control computer program,

wherein at least one context-specific processing pipeline of the plural context-specific pipelines calls the machine-trained language model to classify each of two or more entities specified by the query as a primary entity or a secondary entity, wherein the primary entity has a higher priority than the secondary entity, indicating that the machine-trained language model is to treat the primary entity as an anchor, and then select the secondary entity from among entities that are located near the primary entity,

wherein at least one context-specific processing pipeline of the plural context-specific pipelines includes: identifying, using a routing engine of a multi-engine system, one or more proposed routes based on the query; and validating each proposed route by determining whether the proposed route has a spatial distribution of locations that satisfies a prescribed test, and/or determining whether the proposed route has a travel time that is within a prescribed temporal deviation from a reference travel time, and

wherein at least one context-specific processing pipeline of the plural context-specific pipelines generates an interactive map pertaining to the query, and presents an image that has been retrieved in prescribed proximity to the interactive map.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 5, 2023
From: YANKOV, DRAGOMIR DIMITROV; ZHANG, CHIQUN; KARATZOGLOU, ANTONIOS; CRAIG, HELEN ALTA
To: MICROSOFT TECHNOLOGY LICENSING, LLC
Reel/Frame 064799/0727 →
Continuity (1)
Related Publication 20250076059A1 · Mar 6, 2025
References Cited (42)
US 6256577B1 · Graunke · 2001 [cited by examiner]
US 20040088107A1 · Seligmann · 2004 [cited by examiner]
US 20160258767A1 · Nevrekar et al. · 2016 [cited by applicant]
US 20180157758A1 · Arrizabalaga · 2018 [cited by examiner]
US 20200160148A1 · Garg · 2020 [cited by examiner]
US 20210133195A1 · Jiang · 2021 [cited by examiner]
US 20210182620A1 · Tan · 2021 [cited by examiner]
US 20210287141A1 · Molloy · 2021 [cited by examiner]
US 20210366144A1 · Magistri · 2021 [cited by examiner]
US 20210403036A1 · Danna · 2021 [cited by examiner]
US 20230168101A1 · Carbune · 2023 [cited by examiner]
US 20240126795A1 · Zhong · 2024 [cited by examiner]
EP 1657693A2 · 2006 [cited by examiner]
EP 3748302A1 · 2020 [cited by examiner]
WO WO2019100279A1 · 2019 [cited by examiner]
Álvaro J. Jiménez Palenzuela et al., “Modeling Second Language Acquisition with pre-trained neural language models”, Expert Systems With Applications, vol. 207, Nov. 30, 2022. [cited by examiner]
Jiazhan Feng, et al., “Learning Multi-turn Response Selection in Grounded Dialogues with Reinforced Knowledge and Context Distillation”, ACM Transactions on Information Systems, vol. 41, Issue 4 Article No. 115, Publish… [cited by examiner]
“Find a Location by Query,” available at https://learn.microsoft.com/en-us/bingmaps/rest-services/locations/find-a-location-by-query, Microsoft Corporation, Documentation, Jul. 20, 2022, 15 pages. [cited by applicant]
Brown, et al., “Language Models are Few-Shot Learners,” in 34th Conference on Neural Information Processing Systems (NeurIPS 2020), 2020, 25 pages. [cited by applicant]
“Bing Maps Support,” available at https://www.microsoft.com/en-us/maps/support, Bing Maps support website, Microsoft Corporation, accessed Mar. 11, 2023, 4 pages. [cited by applicant]
Devlin, et al., “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding,” arXiv, arXiv:1810.04805v2 [cs.CL], May 24, 2019, 16 pages. [cited by applicant]
Vaswani, et al., “Attention Is All You Need,” in 31st Conference on Neural Information Processing Systems (NIPS 2017), 2017, 11 pages. [cited by applicant]
“Text Search,” available at https://developers.google.com/maps/documentation/places/web-service/search-text, Google Maps Platform, accessed on Mar. 11, 2023, 26 pages. [cited by applicant]
“Nominatim,” available at https://wiki.openstreetmap.org/wiki/Nominatim, Wikipedia article, accessed on Mar. 12, 2023, 3 pages. [cited by applicant]
Berkhin, et al., “A New Approach to Geocoding: BingGC,” in SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, Article No. 7, Nov. 2015, 10 pages. [cited by applicant]
Craig, et al., Scaling Address Parsing Sequence Models through Active Learning, in SIGSPATIAL '19: Proceedings of the 27th ACM Sigspatial International Conference on Advances in Geographic Information Systems, Nov. 2019… [cited by applicant]
Delling, et al., “Customizable Route Planning in Road Networks,” available at https://www.microsoft.com/en-us/research/publication/customizable-route-planning-in-road-networks/, Jul. 24, 2013, 31 pages. [cited by applicant]
Delling, et al., “Customizable Route Planning in Road Networks,” in Proceedings of the Sixth International Symposium on Combinatorial Search, Jul. 2013, 1 page. [cited by applicant]
Huang, et al., “Active Learning for Transformer Models in Direction Query Tagging,” in SIGSPATIAL '22: Proceedings of the 30th International Conference on Advances in Geographic Information Systems, Article No. 70, Nov.… [cited by applicant]
“Bing Maps REST Services,” available at https://learn.microsoft.com/en-us/bingmaps/rest-services/, Microsoft Corporation, Redmond, WA, Jul. 20, 2022, 2 pages. [cited by applicant]
Ouyang, et al., “Training language models to follow instructions with human feedback,” arXiv, arXiv:2203.02155v1 [cs.CL], Mar. 4, 2022, 68 pages. [cited by applicant]
Shen, et al., “HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face,” arXiv, arXiv:2303.17580v3 [cs.CL], May 25, 2023, 25 pages. [cited by applicant]
Wu, et al., “Visual ChatGPT: Talking, Drawing and Editing with Visual Foundation Models,” arXiv, arXiv:2303.04671v1 [cs.CV], Mar. 8, 2023, 17 pages. [cited by applicant]
“Local Search,” available at https://learn.microsoft.com/en-us/bingmaps/rest-services/locations/local-search, Microsoft Corporation, Redmond, WA, Jul. 20, 2022, 20 pages. [cited by applicant]
“Convex hull,” available at https://en.wikipedia.org/wiki/Convex_hull, Wikipedia article, accessed on Jul. 25, 2023, 18 pages. [cited by applicant]
“Perform geocoding and reverse geocoding,” available at https://learn.microsoft.com/en-us/windows/uwp/maps-and-location/geocoding, Microsoft Corporation, Redmond, WA, Oct. 20, 2022, 4 pages. [cited by applicant]
Radford, et al., “Improving Language Understanding by Generative Pre-Training,” available at https://cdn.openai.com/research-covers/language-unsupervised/language_understanding_paper.pdf, OpenAI, San Francisco, Californ… [cited by applicant]
Touvron, et al., “LLaMA: Open and Efficient Foundation Language Models,” arXiv, Cornell University, arXiv:2302.13971v1 [cs.CL], Feb. 27, 2023, 27 pages. [cited by applicant]
“Graham scan,” available at https://en.wikipedia.org/wiki/Graham_scan, Wikipedia article, accessed on Jul. 25, 2023, 4 pages. [cited by applicant]
“Address geocoding,” available at https://en.wikipedia.org/wiki/Address_geocoding, Wikipedia article, accessed on Jul. 25, 2023, 9 pages. [cited by applicant]
Zhang, et al., “Map GPT Playground: Smart Locations and Routes with GPT,” in SIGSPATIAL '23: Proceedings of the 31st ACM International Conference on Advances in Geographic Information Systems, Article No. 52, Nov. 2023,… [cited by applicant]
International Search Report and Written Opinion for PCT Application No. PCT/US2024/039969, mailing date Nov. 21, 2024, 12 pages. [cited by applicant]