Способы предсказания пунктов назначения из частичных траекторий, применяющие способы моделирования открытого и замкнутого мира

Способы предсказания пунктов назначения из частичных траекторий, применяющие способы моделирования открытого и замкнутого мира

Иллюстрации

Показать все

Реферат

Уровень техники

Местоположение может быть важной частью окружения человека. Огромные количества информации могут быть ассоциативно связаны с географическим местоположением человека и, если человек перемещается, географическим местоположением его пункта назначения. Обычно человек, перемещающийся из одного местоположения в другое местоположение, в типичном варианте использует карту в качестве путеводителя. Однако использование карты может потребовать от человека идентифицировать маршрут, посредством которого можно переместиться из его текущего местоположения в его пункт назначения. Дополнительно, такой путешественник в типичном варианте уведомляется только об информации, относящейся к его текущему местоположению или пункту назначения, на основе устного уведомления, личного знакомства и т.д. В качестве иллюстрации, если путешественник находится в местоположении, где он раньше не был, он может не знать о местоположении заправочной станции, ресторана и т.п. и таким образом может прибегнуть к просьбе о помощи или просмотру знаков вдоль дороги. В качестве дополнительной иллюстрации водитель, который использует карту, может узнать о пробке в дорожном движении, только слушая радиостанцию, которая предоставляет такую информацию.

Обычно доступен ряд приложений, которые поддерживают формирование карты от начальной точки до пункта назначения. Например, такие приложения в типичном варианте могут обеспечить пользователя направлениями движения, а также картой, которая отображает маршрут от начальной позиции до пункта назначения. В качестве иллюстрации пользователь может ввести начальную точку и конечную точку, и приложение может вывести ассоциированные направления движения и/или карту(ы) (например, выделение маршрута). Эти приложения могут использоваться в связи с устройствами, такими как персональные компьютеры, портативные компьютеры, карманные компьютеры, сотовые телефоны и т.п.

Недавно устройства глобальной системы позиционирования (GPS), которые могут определять местоположение, связанное с устройством, стали более широко применяться. Например, GPS может применяться с системой навигации транспортного средства, чтобы предоставить направления движения водителю транспортного средства. Следуя этому примеру, система навигации может отображать карту, которая обновляется согласно изменению позиции транспортного средства. Дополнительно система навигации может обеспечить водителю пошаговые направления, пока транспортное средство перемещается (например, через дисплей, динамик и т.д.). Однако традиционные системы, применяющие GPS (так же, как и другие традиционные технологии) в типичном варианте, требуют от пользователя непосредственно ввести пункт назначения. Например, устройство GPS обычно не предоставит направления движения водителю транспортного средства, пока водитель не укажет местоположение пункта назначения. Дополнительно, пользователи могут не вводить пункт назначения каждый раз, когда они перемещаются; таким образом предупреждения, связанные с пунктом назначения и/или ассоциированным маршрутом, могут не предоставляться пользователям. Например, пользователь может не ввести пункт назначения при своем движении в местоположение, к которому он часто передвигается, такому как работа, дом, школа и т.д.; соответственно, соответствующие предупреждения могут не предоставляться пользователю.

Сущность изобретения

Последующий текст представляет упрощенное краткое описание, чтобы предоставить основное понимание некоторых аспектов, описанных в данном документе. Это краткое описание не является всесторонним обзором заявленной сущности изобретения. Оно не предназначено, ни чтобы определять ключевые или критические элементы заявленной сущности изобретения, ни очерчивать его объем. Его единственной целью является представить в упрощенном виде некоторые концепции в качестве вступления к более подробному описанию, которое представлено позже.

Заявленная сущность изобретения относится к системам и/или способам, которые облегчают вероятностное предсказание пункта(ов) назначения. Могут быть получены входные данные, которые могут относиться к пользователю, истории пользователя (например, исторические данные), к отдельным пользователям, топографии географической области (например, данные о свойствах местности), оптимальным маршрутам, распределению времени передвижения, текущему передвижению (например, местоположению, изменению местоположения, времени) и т.д. Предполагается, что входные данные могут быть получены из любого источника (например, компонент местоположения, компонент таймера, хранилище данных, Интернет). Предсказание может быть совершено с использованием одних или более априорных данных и/или одной или более вероятностей. Например, априорными данными могут быть априорные данные о персональных пунктах назначения и/или априорные данные о свойствах местности. Дополнительно, вероятности могут быть вероятностью оптимального движения и/или вероятностью времени передвижения. Следует принимать во внимание, что одни или более априорных данных, одна или более вероятностей или комбинация априорных данных и вероятностей могут использоваться, чтобы сформировать предсказанный(ные) пункт(ы) назначения.

В соответствии с различными аспектами заявленной сущности изобретения компонент оценки пункта назначения может вероятностно предсказать пункт назначения для передвижения на основе априорных данных и/или вероятности(ей). Компонент оценки пункта назначения может применяться, чтобы выбрать и/или объединить априорные данные и/или вероятность(и), чтобы вывести предсказанные пункты назначения. Согласно примеру любая комбинация априорных данных и/или вероятностей может применяться компонентом оценки пункта назначения посредством использования правила Байеса.

Следуя одному или более аспектам заявленного предмета изобретения, компонент оценки пункта назначения может применить априорные данные о персональных пунктах назначения, априорные данные о свойствах местности, вероятность оптимального движения и/или вероятность времени передвижения. Априорные данные о персональных пунктах назначения могут быть основаны на предыдущих пунктах назначения пользователя; таким образом исторические данные могут быть оценены, чтобы вывести априорные данные о персональных пунктах назначения. Например, моделирование открытого мира и/или моделирование замкнутого мира может применяться в связи с получением априорных данных о персональных пунктах назначения. Анализ открытого мира и/или анализ замкнутого мира могут быть объединены в прогноз местоположения; таким образом анализ может включать в себя предсказание как вероятности того, что водитель посетит ранее не наблюдавшееся местоположение (в качестве функции горизонта наблюдения), так и пространственных соотношений новых местоположений, заданных априорными местоположениями. Параметры для логического вывода на основе открытого мира могут получаться из наблюдения за множеством людей во времени и затем могут быть отображены конкретным людям. Также при моделировании открытого мира может рассматриваться демографическая информация. Дополнительно, априорные данные о свойствах местности могут быть основаны на данных о свойствах местности, которые предоставляют вероятность того, что отдельная ячейка является пунктом назначения на основе свойств местности в отдельной ячейке. Кроме того, вероятность эффективного движения может быть основана на изменении времени до прибытия в возможный пункт назначения, где можно предположить, что путешественник продолжит сокращать количество времени до прибытия по мере продолжения передвижения. Например, вычисленная эффективность движения, ассоциированная с каждым возможным пунктом назначения, может быть использована как сведения о конечном пункте назначения. Вероятность времени передвижения может быть основана на распределении времени передвижения и/или пройденном времени передвижения. Согласно дополнительному примеру как часть анализа могут использоваться контекстно-зависимые признаки, такие как время дня, день недели (например, выходные против буднего дня), праздник, время года, месяц года и т.д.

Согласно различным аспектам заявленной сущности изобретения обоснование может быть применено, чтобы идентифицировать пункты назначения, маршруты, которые люди, вероятно, примут в качестве своего пути до пунктов назначения и т.п. Кроме того, приложения могут использовать идентифицированные пункты назначения и/или маршруты, чтобы предоставить соответствующую информацию пользователю. Согласно примеру приложения могут предоставить предупреждения относительно дорожного движения, строительства, проблем с безопасностью впереди, отображаемых указателей, предоставлять направления, совет по маршруту, обновления и т.д. Например, информация, предоставленная пользователю, может относиться к предсказанному(ым) пункту(ам) назначения. Дополнительно или альтернативно, маршруты до предсказанного(ых) пункта(ов) назначения могут быть оценены так, что информация может относиться к местоположениям, ассоциированным с маршрутами (например, местоположению, проходящему вдоль маршрута). Соответствующая информация может включать в себя, например, предупреждения, относящиеся к движению, помощь в навигации, события, целевую рекламу, учреждения, дорожные знаки и т.п. Следует принимать во внимание, что соответствующая информация может быть получена любым образом (например, посредством аудиосигнала, визуальной информации и т.д.). Кроме того, предоставляемая информация может быть индивидуально подстроена на основе связанных с пользователем предпочтений.

Последующее описание и прилагаемые чертежи подробно излагают определенные иллюстративные аспекты заявленной сущности изобретения. Эти аспекты, тем не менее, указывают только на некоторые из множества способов, которыми могут быть использованы принципы такой сущности изобретения, и заявленная сущность изобретения включает в себя все такие аспекты и их эквиваленты. Другие преимущества и новые признаки изобретения станут явными из следующего подробного описания изобретения, если рассматривать их вместе с чертежами.

Краткое описание чертежей

Фиг.1 иллюстрирует блок-схему примерной системы, которая облегчает определение пункта(ов) назначения пользователя.

Фиг.2 иллюстрирует блок-схему примерной системы, которая формирует вероятностную координатную сетку и/или маршрут(ы) между местоположениями, которые могут использоваться в связи с вероятностным предсказанием пункта(ов) назначения.

Фиг.3 иллюстрирует блок-схему примерной системы, которая предсказывает пункт(ы) назначения на основе исторических данных.

Фиг.4 иллюстрирует блок-схему примерной системы, которая использует моделирование открытого мира, чтобы предсказать пункт(ы) назначения.

Фиг.5 иллюстрирует блок-схему примерной системы, которая предсказывает пункт(ы) назначения на основе, по меньшей мере, частично, данных о свойствах местности.

Фиг.6 иллюстрирует пример 4-уровневого распределения вероятности с дискретизацией по четырем пороговым радиусам от ранее посещенного местоположения.

Фиг.7 иллюстрирует блок-схему примерной системы, которая выводит предсказания пункта(ов) назначения на основе, по меньшей мере, частично, данных об эффективном маршруте.

Фиг.8 иллюстрирует блок-схему примерной системы, которая оценивает время передвижения в связи с предсказанием пункта(ов) назначения.

Фиг.9 иллюстрирует блок-схему примерной системы, которая позволяет объединять априорные данные и/или вероятность(и), чтобы облегчить предсказание пункта(ов) назначения.

Фиг.10 иллюстрирует блок-схему примерной системы, которая предоставляет информацию, которая может относиться к предсказанному пункту(ам) назначения.

Фиг.11 иллюстрирует блок-схему примерной системы, которая вероятностно предсказывает пункт(ы) назначения во время передвижения.

Фиг.12 иллюстрирует блок-схему примерной системы, которая облегчает формирование предсказанного пункта(ов) назначения.

Фиг.13 иллюстрирует примерную методологию, которая облегчает вероятностное предсказание пункта(ов) назначения.

Фиг.14 иллюстрирует примерную методологию, которая предоставляет информацию, относящуюся к пункту назначения, который может быть предсказан на основе априорных данных и/или вероятности(ей), которые могут быть объединены.

Фиг.15-18 иллюстрируют примерные координатные сетки и соответствующие карты, изображающие различные аспекты в ассоциативной связи с моделированием поведения водителя и предсказаниями пункта назначения.

Фиг.19 иллюстрирует типичную сетевую среду, в которой могут быть использованы новые аспекты заявленного предмета изучения.

Фиг.20 иллюстрирует примерную операционную среду, которая может быть использована в соответствии с заявленным предметом изучения.

Подробное описание вариантов осуществления изобретения

Заявляемый предмет изобретения описан со ссылками на чертежи, на которых одинаковые ссылочные позиции используются для ссылок на одинаковые элементы. В последующем описании, для целей пояснения, многие конкретные детали изложены для того, чтобы обеспечить полное понимание настоящего изобретения. Тем не менее, очевидно, что заявляемая сущность изобретения может быть использована на практике без этих конкретных деталей. В иных случаях хорошо известные структуры и устройства показаны в форме блок-схем, чтобы упростить описание настоящего изобретения.

При использовании в этом документе термины «компонент», «система» и тому подобные предназначены, чтобы ссылаться на связанный с компьютером объект, либо аппаратные средства, либо программное обеспечение (например, в ходе выполнения) и/или микропрограммное обеспечение. Например, компонентом может быть процесс, запущенный на процессоре, процессор, объект, исполняемый файл, программа и/или компьютер. В качестве иллюстрации, приложение, запущенное на сервере, и сервер могут быть компонентом. Один или более компонентов могут постоянно находиться внутри процесса, и компонент может быть локализован на компьютере и/или распределен между двумя и более компьютерами.

Дополнительно, заявляемая сущность изобретения может быть реализована в виде способа, устройства или изделия с использованием стандартных технологий программирования и/или проектирования для производства программного обеспечения, микропрограммного обеспечения, аппаратных средств или любого их сочетания, чтобы управлять компьютером для реализации раскрытой сущности изобретения. Термин "изделие" при использовании в данном документе служит для того, чтобы охватывать компьютерную программу, доступную из любого машиночитаемого устройства, носителя или среды. Например, машиночитаемые носители могут включать в себя, но не ограничиваться этим, магнитные устройства хранения (например, жесткий диск, гибкий магнитный диск, магнитную ленту и т.д.), оптические диски (к примеру, компакт-диск (CD), цифровой многофункциональный диск (DVD)), смарт-карты и устройства флэш-памяти (к примеру, карта, флэш-драйвы). Дополнительно, должно быть принято во внимание, что несущая волна может быть использована, чтобы переносить машиночитаемые электронные данные, такие как используемые при передаче и приеме электронной почты или при осуществлении доступа к сети, такой как Интернет или локальная сеть (LAN). Конечно, специалисты в данной области техники будут отдавать себе отчет, что многие модификации могут быть сделаны по отношению к этой конфигурации не выходя из объема и сущности заявленного изобретения. Кроме того, слово «примерный» используется в материалах настоящей заявки, чтобы означать "служащий в качестве примера, экземпляра или иллюстрации". Любой аспект или конструкция, описанные в материалах настоящей заявки как «примерные», необязательно должны быть истолкованы в качестве предпочтительных или преимущественных над другими аспектами или конструкциями.

Фиг.1 иллюстрирует систему 100, которая облегчает определение пункта(ов) назначения пользователя. Система 100 включает в себя компонент 102 интерфейса, который принимает входные данные, которые могут относиться к пользователю, пользовательской истории, топографии географической области, передвижению, оптимальному маршруту и т.д. Компонент 102 интерфейса может принимать входные данные от любого источника. Например, компонент 102 интерфейса может получать входные данные от любого компонента (не показан), который позволяет определение местоположения и/или изменение в местоположении пользователя, такого как, например, компонент, который поддерживает систему глобального позиционирования (GPS), систему спутниковой навигации, ГЛОНАСС, Galileo, Европейскую геостационарную дополнительную навигационную систему (EGNOS), Beidou, навигационную систему Декка-Навигатор, триангуляцию между вышками связи и т.д. В качестве дополнительной иллюстрации, компонент 102 интерфейса может принимать входные данные, ассоциативно связанные с пунктами назначения, к которым пользователь двигался ранее (например, из хранилища данных, посредством пользовательского ввода). Дополнительно или альтернативно, компонент 102 интерфейса может получать входные данные от компонента таймера (не показан), который может определить количество времени, в течение которого пользователь передвигается в настоящее время (например, в течение текущего передвижения). Кроме того, компонент 102 интерфейса может принять данные о свойствах местности; например, такие данные могут быть получены из хранилища данных (не показано). Следует принимать во внимание, что компонент 102 интерфейса может принимать входные данные в любое время; например, входные данные могут быть получены компонентом 102 интерфейса в процессе передвижения пользователя (например, в реальном времени) перед тем, как пользователь начинает передвижение, и т.д.

Входные данные могут быть предоставлены компонентом 102 интерфейса компоненту 104 оценки пункта назначения, который может оценить входные данные и вероятностно предсказать пункт(ы) назначения. Компонент 104 оценки пункта назначения может сформировать предсказанный(ые) пункт(ы) назначения с помощью априорных данных и/или вероятности(ей) на основе, по меньшей мере, частично, входных данных. Например, компонент 104 оценки пункта назначения может применять априорные данные о персональных пунктах назначения, априорные данные о свойствах местности, вероятность эффективного движения и/или вероятность времени передвижения. Следует принимать во внимание, что любое число априорных данных и/или вероятностей может применяться в комбинации, чтобы вывести предсказанный(ые) пункт(ы) назначения. В качестве иллюстрации, компонент 104 оценки пункта назначения может использовать только априорные данные о свойствах местности, чтобы вероятностно предсказать пункт назначения, ассоциативно связанный с передвижением. Согласно другому примеру компонент 104 оценки пункта назначения может применять априорные данные о персональных пунктах назначения, априорные данные о свойствах местности, вероятность эффективного движения и вероятность времени передвижения, чтобы вероятностно предсказать пункт(ы) назначения. Следует принимать во внимание, что заявленная сущность изобретения не ограничена этими примерами.

Компонент 104 оценки пункта назначения может оценить данные от различных источников, чтобы предсказать местоположение, к которому перемещается человек. Согласно иллюстрации компонент 104 оценки пункта назначения может вероятностно предсказать пункт назначения перед началом передвижения (например, когда пользователь садится в машину) или в любое время в процессе передвижения. Таким образом, входные данные могут включать в себя данные, относящиеся к текущему передвижению (например, текущее местоположение, изменение в местоположении, любое число местоположений, ассоциированных с текущим передвижением, количество времени, ассоциированное с текущим передвижением и т.д.). Кроме того, согласно примеру в процессе такого передвижения компонент 104 оценки пункта назначения может использовать входные данные из передвижения, чтобы динамически обновлять предсказание(я) пункта(ов) назначения. Альтернативно, компонент 104 оценки пункта назначения может анализировать входные данные, которые испытывают недостаток информации, ассоциированной с текущим передвижением пользователя, и соответственно вывести предсказания на основе разнородной информации (например, данных о свойствах местности, исторических данных и т.д.).

Компонент 104 оценки пункта назначения может вывести предсказанный пункт(ы) назначения, как иллюстрировано. Дополнительно, предполагается, что предсказанный(ые) пункт(ы) назначения может (могут) быть предоставлен(ы) компоненту 102 интерфейса компонентом 104 оценки пункта назначения и компонент 102 интерфейса может вывести предсказание(я) пункта(ов) назначения. Следует принимать во внимание, что предсказанные пункты назначения могут быть предоставлены пользователю. Согласно примеру пользователю может быть предоставлена карта, которая отображает предсказанный пункт назначения. Дополнительно, карта может включать в себя информацию, такую как курс, пройденный до сих пор в течение текущего передвижения, и/или направления, ассоциированные с оставшейся частью передвижения, чтобы достичь предсказанного(ых) пункта(ов) назначения. Такая карта может также представлять информацию для целевой рекламы; такое рекламное содержимое может выборочно выводиться на основе соображений пользовательских предпочтений (например, пользователь предпочитает бензин A бензину B, скорее ресторан C быстрого питания, чем ресторан D быстрого питания). Предполагается, что предсказанные пункты назначения могут быть предоставлены пользователю с помощью любого типа звукового и/или визуального сигнала. Кроме того, пользователь может обеспечить обратную связь, ассоциированную с предсказанными пунктами назначения (например, выбор одного пункта назначения из набора предсказанных пунктов назначения, указание, что предсказанный пункт назначения неправильный и т.д.). Согласно другой иллюстрации предсказание(я) пункта(ов) назначения может (могут) быть передано(ы) отдельному компоненту (не показан), который может использовать предсказание(я), чтобы вывести соответствующую информацию (например, близкие точки интереса, услуги на основе местоположения, метеоинформация, относящаяся к пункту(ам) назначения, информация дорожного движения, связанная с пунктом(ами) назначения, целевая реклама, информация, связанная с событиями и другая), которая может впоследствии быть представлена пользователю (например, через предупреждения).

Компонент 104 оценки пункта назначения может оценить вероятные пункты назначения на основе, по меньшей мере, частично, данных о растительном покрове, факте того, что путешественники (например, водители) в типичном варианте используют эффективные маршруты, и/или измеренного распределения времен передвижения. Дополнительно, компонент 104 оценки пункта назначения может объединить эти сигналы (например, входные данные) с помощью правила Байеса, чтобы вероятностно предсказать пункт(ы) назначения. Кроме того, компонент 104 оценки пункта назначения может принимать во внимание предыдущий(е) пункт(ы) назначения (например, исторические данные) пользователя и/или других пользователей; однако заявленная сущность изобретения не ограничена вышеупомянутыми примерами. Компонент 104 оценки пункта назначения может также улучшить точность по времени, так как получены обучающие данные, ассоциированные с пользователем. Согласно другому примеру компонент 104 оценки пункта назначения может позволить определять местоположения возможных пунктов назначения, где угодно. Согласно другой иллюстрации компонент 104 оценки пункта назначения может ограничивать возможные пункты назначения дорожной сетью; таким образом точность может быть увеличена, так как многие фактические пункты назначения находятся у дороги или рядом с дорогой. Однако заявленная сущность изобретения не ограничена таким образом. Также компонент 104 оценки пункта назначения может принимать во внимание контекстно-зависимую информацию, такую как, например, время дня, день недели (например, выходные против буднего дня), праздник, время года, месяц года и т.д.

Хотя компонент 102 интерфейса изображен как отдельный от компонента 104 оценки пункта назначения, предполагается, что компонент 104 оценки пункта назначения может включать в себя компонент 102 интерфейса или его часть. Также компонент 102 интерфейса может предоставлять различные адаптеры, компоненты, каналы, каналы связи и т.д., чтобы предоставить возможность взаимодействия с компонентом 104 оценки пункта назначения.

Знание индивидуума (например, водителя) о пункте назначения может быть важным параметром для получения полезной информации, пока человек перемещается (например, во время поездки). Например, система навигации в машине может автоматически отобразить дорожные пробки, заправочные станции, рестораны и другие точки интереса, которые водитель ожидает встретить во время передвижения. Дополнительно, если система навигации может создать точное предположение об общем регионе, в который направляется водитель, то она может разумно отфильтровать информацию, которую она отображает, уменьшая таким образом познавательную нагрузку. Кроме того, хотя может быть возможно явно запросить водителя о его пункте назначения, полезным является уменьшение опрашивания водителя для предоставления этой информации в начале каждого передвижения. Система 100 способна реализовать автоматическое предсказание пунктов назначения, например, путем использования алгоритма, чтобы предсказать пункты назначения движения на основе интуиции, что водитель примет довольно эффективный маршрут до пункта назначения. Согласно аспекту предсказания могут быть сформированы без моделирования поведения индивидуума в процессе передвижения (например, предполагая отсутствие априорных знаний об обычных пунктах назначения водителя, таких как работа, дом, школа и т.д.); однако заявленная сущность изобретения не ограничена таким образом. Согласно этому примеру система 100 может использоваться в новом транспортом средстве, сдаваемом на прокат транспортном средстве или в городе, который водитель ранее не посещал.

На фиг.2 иллюстрируется система 200, которая формирует вероятностную координатную сетку и/или маршрут(ы) между местоположениями, которые могут использоваться в связи с вероятностным предсказанием пункта(ов) назначения. Система 200 может включать в себя компонент 102 интерфейса, который получает входные данные и предоставляет входные данные компоненту 104 оценки пункта назначения. Компонент 104 оценки пункта назначения может вероятностно предсказать пункт(ы) назначения, ассоциированный(е) с входными данными. Компонент 104 оценки пункта назначения может использовать вероятностную координатную сетку, сформированную компонентом 202 координатной сетки, и/или любое число маршрутов между местоположениями (и любые данные, ассоциированные с ними), выведенные компонентом 204 планирования маршрута, чтобы идентифицировать вероятный пункт(ы) назначения.

Согласно примеру компонент 202 координатной сетки может формировать вероятностную координатную сетку, которая может быть ассоциирована с картой. Например, двумерная координатная сетка квадратов (например, ячеек) может быть ассоциирована с картой так, что квадраты (например, ячейки) могут относиться к любой фактической физической географической области (например, 1 километр связан с каждой стороной каждого из квадратов координатной сетки). Дополнительно, предполагается, что координатная сетка, выведенная компонентом 202 координатной сетки, может включать в себя ячейки любой формы (например, многоугольник с M сторонами, где M - положительное целое число, большее чем два, круг, и т.п.) или формы, отличные от или в дополнение к квадратным ячейкам. Ячейки могут представлять дискретное местоположение и могут быть ассоциированы с любым фрагментом изображения, размером и числом. Каждой ячейке может быть назначен уникальный индекс (например, z'=1, 2, 3,…, N, где N является любым положительным целым числом), и компонент 104 оценки пункта назначения может идентифицировать ячейку или ячейки, в которых пользователь, вероятно, закончит передвижение (например, пункт назначения).

Компонент 104 оценки пункта назначения может вычислить для каждой ячейки вероятность того, что она является пунктом назначения. Например, вероятности могут быть определены посредством оценки P(D=i|X=x), где D - случайная переменная, представляющая пункт назначения, а X - случайная переменная, представляющая вектор наблюдаемых признаков передвижения к настоящему моменту времени. Дополнительно, могут использоваться вероятности и/или априорные данные, и может быть применено правило Байеса, чтобы вывести следующее:

Соответственно, N может быть числом ячеек в координатной сетке, а P(D=i) может быть априорной вероятностью того, что пунктом назначения является ячейка i. Априорная вероятность может быть вычислена, например, с помощью априорных данных о персональных пунктах назначения и/или априорных данных о свойствах местности. Кроме того, P(X=x|D=i) может быть вероятностью того, что ячейка i является пунктом назначения на основе наблюдаемого измерения X, которое может быть вычисленной картографической информацией от различных источников. Например, вероятность может быть вероятностью эффективного движения и/или вероятностью времени передвижения. Знаменатель может быть нормирующим множителем, который может быть вычислен для суммирования вероятностей всех ячеек, чтобы сумма равнялась единице.

Компонент 204 планирования маршрута может предоставить маршруты между парами ячеек и/или оценки времен движения между каждой парой ячеек в координатной сетке, сформированной компонентом 202 координатной сетки. Компонент 204 планирования маршрута может аппроксимировать время движения с помощью Евклидова расстояния и аппроксимации скорости между каждой парой ячеек. Дополнительно или альтернативно, компонент 204 планирования маршрута может планировать маршрут движения между центральными точками (широта, долгота) пар ячеек, чтобы вывести более точную оценку времени движения. Таким образом, компонент 204 планирования маршрута может предоставить выходные данные на основе, по меньшей мере, частично, дорожной сети и ограничений скорости между ячейками.

На фиг.3 иллюстрируется система 300, которая предоставляет предсказанный(ые) пункт(ы) назначения на основе, по меньшей мере, частично, данных о свойствах местности. Система 300 содержит компонент 102 интерфейса, который принимает входные данные, которые могут включать в себя данные о свойствах местности. Система 300 также включает в себя компонент 104 оценки пункта назначения, который может формировать предсказанный(ые) пункт(ы) назначения на основе, по меньшей мере, частично, априорных данных о свойствах местности, сформированных компонентом 302 свойств местности.

Компонент 302 свойств местности может облегчить оценку вероятности того, что ячейка является пунктом назначения, на основе данных о свойствах местности, связанных с отдельной ячейкой. Априорные данные о свойствах местности могут быть связаны с топологией, относящейся к местоположению. Например, середины озер и океанов являются редкими пунктами назначения для водителей, а коммерческие площади являются более привлекательными пунктами назначения, чем места, вечно покрытые льдом и снегом. Компонент 102 интерфейса, например, может облегчить получение карты с данными о свойствах местности, которая может позволить компоненту 302 свойств местности характеризовать ячейки в координатной сетке на основе карты местности географической съемки Соединенных Штатов (USGS); однако заявленная сущность изобретения не ограничена таким образом, и предполагается, что ячейки могут характеризоваться с помощью любых данных о свойствах местности. Например, карты свойств местности USGS могут категоризировать каждый квадрат размером 30 м × 30 м Соединенных Штатов по одному типу из двадцати одного типа (например, детализирующие травянистые заболоченные местности, лесистые заболоченные местности, фруктовые сады, многолетние льды, зерновые, пашни, голые скалы, земли под паром, городские территории, жилые районы с высокой интенсивностью, переходные районы, карьеры, вода, луга, смешанный лес, кустарники, лиственный лес, вечнозеленый лес, жилые районы с низкой интенсивностью, коммерческая площадь и т.д.) свойств местности. Компонент 302 свойств местности может оценить широту и/или долготу каждого пункта назначения передвижения в наборе данных, чтобы создать упорядоченную гистограмму по типам свойств местности (например, двадцать один тип свойств местности), например. Вода может быть непопулярным пунктом назначения, хотя более популярным, чем некоторые другие категории (например, травянистые заболоченные местности, лесистые заболоченные местности и т.п.), а коммерческие площади могут быть более привлекательными, чем покрытые льдом и снегом. Два наиболее популярных пункта назначения могут быть типами "коммерческий" и "жилой район с низкой интенсивностью", которые USGS описывает как

"Коммерческий/промышленный/транспортный" - включает в себя инфраструктуру (например, дороги, железные дороги) и все высокоразвитые области, не классифицированные как "жилой район с высокой интенсивностью".

"Жилой район с низкой интенсивностью" включает в себя области со смешением созданных материалов и растительностью. Созданные материалы составляют 30-80 процентов поверхности. Растительность может составлять 20-70 процентов поверхности. Эти области наиболее обычно включают в себя жилые единицы на одну семью. Плотность населения будет ниже, чем в "жилых районах с высокой интенсивностью".

Категория "вода" может быть ассоциирована с ненулевой вероятностью, так как квадрат USGS 30 м × 30 м может быть категоризирован как вода, даже если он имеет вплоть до 25% суши, которая может включать в себя свойства пляжей и берегов в зависимости от того, как расположены квадраты. Предполагается, что разные регионы могут быть ассоциированы с разными сочетаниями свойств местности, и постоянные жители несопоставимых регионов могут, возможно, иметь разные линии поведения в отношении типов свойств местности.

Согласно примеру компонент 302 свойств местности может определить вероятность ячейки пункта назначения, если она полностью покрыта типом j свойства местности для j = 1, 2, 3, …, 21 посредством оценки P(D=i|G=j). Согласно иллюстрации, если компонент 302 свойств местности использует вероятностную координатную сетку с ячейками 1 км × 1 км, каждая ячейка может содержать около 1111 меток свойств местности 30 м × 30 м (например, часто ячейки могут не быть полностью покрыты одним и тем же типом). Для каждой ячейки компонент 302 свойств местности может вычислить распределение типов свойств местности, которое может упоминаться как P_i(G=j). В качестве иллюстрации, компонент 302 свойств местности может вычислить априорную вероятность каждой ячейки посредством исключения типов свойств местности в ячейке:

Вероятность P_G(D=i) может быть связана с априорной вероятностью ячейки пункта назначения на основе свойств местности. Соответственно, компонент 302 свойств местности может определить, что вода и сельские области, например, могут быть менее вероятными пунктами назначения. Априорные данные о свойствах местности, сформированные компонентом 302 свойств местности (и априорные данные о персональных пунктах назначения, полученные с помощью компонента истории пользователя, такого как описанный ниже), могут предоставить распределения априорной вероятности, так как они в типичном варианте не основаны на измеренных признаках текущей поездки пользователя.

На фиг.4 иллюстрируе