SYSTEM AND METHOD FOR RECOMMENDING AN OPTIMAL ROUTE

System and method for recommending an optimal route to a user are disclosed. In one embodiment, the method comprises receiving a potential travel request from the user. The method further comprises generating regional context data by analyzing the potential travel request and generating cost context data based on the regional context data. The cost context data comprises at least one potential route. The method further comprises correlating the potential travel request, the regional context data and the cost context data to obtain travel context data. The method further comprises determining the optimal route amongst the at least one potential route by applying one or more rules to a user profile and the travel context data and dynamically updating the optimal route based on at least one of presence of one or more passengers in a vehicle and High Occupancy Vehicle (HOV) lane data.

TECHNICAL FIELD

This disclosure relates generally to a navigation device and more particularly to a system and a method for recommending an optimal route to a user.

BACKGROUND

These days navigation devices typically receive input from a user and recommend a route along with traffic information. Most of conventional navigation systems do not consider various factors, such as High Occupancy Vehicle lane availability, preferences of other passengers in a vehicle, and cost of travel. A high occupancy vehicle lane (HOV lane) is a restricted traffic lane reserved at peak travel times or longer for the exclusive use of vehicles with a driver and one or more passengers, including carpools, vanpools, and transit buses. Further, typically a user is required to manually enter some of these factors or use information acquired manually from alternate sources, There are vehicle navigation systems that determine the number of vehicle occupants, and accordingly includes or excludes HOV restricted sections of road in route calculations. However, the conventional navigation systems may not recommend an optimal route in case more than one passenger is travelling is vehicle as passenger preferences are not considered.

SUMMARY

In one embodiment, a method for recommending an optimal route to a user is disclosed. The method comprises receiving a potential travel request from the user. The potential travel request comprises a start location, an end location, and a time of departure from the start location. The method further comprises generating regional context data by analyzing the potential travel request. The method further comprises generating cost context data based on the regional context data. The cost context data comprises at least one potential route from the start location to the end location. Each of the at least one potential route is associated with a travel time and a travel cost value. The method further comprises correlating the potential travel request, the regional context data and the cost context data to obtain travel context data. The method further comprises determining the optimal route amongst the at least one potential route by applying one or more rules to a user profile and the travel context data. The method further comprises dynamically updating the optimal route, to be recommended to the user, based on at least one of presence of one or more passengers in a vehicle and High Occupancy Vehicle (HOV) lane data.

In another embodiment, a system for recommending an optimal route to a user is disclosed. The system includes at least one processors and a computer-readable medium. The computer-readable medium stores instructions that, when executed by the at least one processor,cause the at least one processor to perform operations comprising receiving a potential travel request from the user. The potential travel request comprises a start location, an end location, and a time of departure from the start location. The operations further comprise generating regional context data by analyzing the potential travel request. The method further comprises generating cost context data based on the regional context data. The cost context data comprises at least one potential route from the start location to the end location. Each of the at least one potential route is associated with a travel time and a travel cost value. The operations further comprise correlating the potential travel request, the regional context data and the cost context data to obtain travel context data. The operations further comprise determining the optimal route amongst the at least one potential route by applying one or more rules to a user profile and the travel context data. The operations further comprise dynamically updating the optimal route, to be recommended to the user, based on at least one of presence of one or more passengers in a vehicle and High Occupancy Vehicle (HOV) lane data.

In another embodiment, a non-transitory computer-readable storage medium for recommending an optimal route to a user is disclosed, which when executed by a computing device, cause the computing device to perform operations comprising receiving a potential travel request from the user. The potential travel request comprises a start location, an end location, and a time of departure from the start location. The operations further comprise generating regional context data by analyzing the potential travel request. The method further comprises generating cost context data based on the regional context data. The cost context data comprises at least one potential route from the start location to the end location. Each of the at least one potential route is associated with a travel time and a travel cost value. The operations further comprise correlating the potential travel request, the regional context data and the cost context data to obtain travel context data. The operations further comprise determining the optimal route amongst the at least one potential route by applying one or more rules to a user profile and the travel context data. The operations further comprise dynamically updating the optimal route, to be recommended to the user, based on at least one of presence of one or ore passengers in a vehicle and High Occupancy Vehicle (HOV) lane data.

DETAILED DESCRIPTION

Exemplary embodiments are described with reference to the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are possible without departing from the spirit and scope of the disclosed embodiments, Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein and in the appended claims, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise.

The present subject matter discloses systems and methods for recommending an optimal route to a user. In the present subject matter, the systems and methods leverage various Internet of Things (IoT) technologies, and information such as user preferences, user profile data and regional statistics data (Big Data), user social media data, and analytics data generated based on the user profile to arrive at a context which shall be used for arriving at optimal routing to destinations and also enable the external navigation devices to access this in arriving similar routing. Further, the present subject matter discloses use of additional sensors, such as occupancy counter, finger print reader, ECG reader, voice recognition, notification from various devices in a smart home, notification from user's social media feeds, and face recognition to identify number of passengers in a vehicle. Further, information, such as personal data like calendar, meeting invites, TO-DO list received from user devices are used to determine the destination and recommend an optimal route. The present subject matter also considers cost based analysis of routes which includes variable factors like Fuel consumption, Traffic prediction, Toll Gates, Occupancy, Current prevailing Gas price etc.

Working of the systems and methods for reco mending an optimal route to a user is described in conjunction withFIGS. 1-3. It should be noted that the description and drawings merely illustrate the principles of the present subject matter. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the present subject matter and are included within its spirit and scope. Furthermore, all examples recited herein are principally intended expressly to be only for pedagogical purposes to aid the reader in understanding the principles of the present subject matter and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the present subject matter, as well as specific examples thereof, are intended to encompass equivalents thereof. While aspects of the systems and methods can be implemented in any number of different computing systems environments, and/or configurations, the embodiments are described in the context of the following exemplary system architecture(s).

FIG. 1illustrates an exemplary network environment100comprising a navigation system102, in accordance with some embodiments of the present disclosure.

In an example, the navigation system102may be implemented on variety of computing systems. Examples of the computing systems may include a laptop computer, a smart phone, a tablet, a notebook, a smart device, a wearable device, and the like. Although the description herein is with reference to certain computing systems, the systems and methods may be implemented in other computing systems, albeit with a few variations, as will be understood by a person skilled in the art.

As shown inFIG. 1, the navigation system102comprises various computational units, such as a user profiler104, a regional statistical analyzer106, a rule engine108, a correlation unit110, an automation engine112, and a navigation module114.

Further, the navigation system102is communicatively coupled to a display unit116and an external navigation module118. The display unit116is used to display an optimal route to the user along with additional information, such as travel time, weather condition, and travel cost. Examples of the external navigation module118may include navigation devices, such as Mobile Maps™, TomTom™, and Garmin™. The external navigation module118may provide base navigation data to the navigation module114present in the system102to build potential routes. The external navigation module118may also display routes with way points as provided by navigation module114.

Although all the display unit116is shown external to the navigation system102inFIG. 1, it may be noted that, in one implementation, that the display unit116may be present within the navigation system102. Hereinafter, the navigation system102may be interchangeably referred to as system102.

In an example, the system102may communicate with the external navigation module118through a network. The network may be a wireless network, wired network or a combination thereof. The network can be implemented as one of the different types of networks, such as intranet, local area network (LAN), wide area network (WAN), the internet, and such. Further, the network may include a variety of network devices, including routers, bridges, servers, computing devices, storage devices, etc.

In operations, to recommend an optimal route to a user, the user profiler104may receive a potential travel request from the user. In an example, the potential travel request may comprise a start location, an end location, and a time of departure from the start location. In another example, to determine the potential travel request, the user profiler104may analyze a user profile indicating user preferences, past travel requests, social profiles, a to-do list, calendar invites, and a mode of travel. The user profiler104is responsible for retrieving user related from various sources and identifying aspects which is important for determining the optimal route, such as calendar Invites, social profiles, user preferences, user settings and user profile information. It may be noted that receiving of the potential travel request is not limited to the user. In an example, the potential travel request may be identified based on information received from sources, such as smart home automation system. Further, the potential travel request may be then received by the user profiler104.

In an example, the user profiler104may receive the potential travel request when the user is entering the vehicle or when the user is entering an address into the system102. In another example, the user profiler104may determine the potential travel request based on personal routine of user, such as going to office, returning home, and going to gym. Also, the user profiler104may consider personal Itinerary notifications for upcoming travels by accessing calendar or to-do list of the user.

In one embodiment, the user profiler104may receive the potential travel request when a meeting request notification is identified that has a meeting location different from current geographic location. In another embodiment, the user profiler104may receive the potential travel request when a smart home gateway provides data from a Smart Refrigerator on Low supplies. In such cases, the potential travel request may include way point to a preferred or to a closest grocery store, as the case maybe.

Once the potential travel request is received, the regional statistics analyzer may generate regional context data by analyzing the potential travel request. In an example, to generate the regional context data, the regional statistical analyzer106may extract at least one region to be covered during the travel based on the potential travel request. Thereafter, the regional statistical analyzer106may determine traffic conditions, number of tolls, modes of transport, the High Occupancy Vehicle (HOV) lane data, public transport details, and fuel price in the at least one region in order to generate the regional context data. The HOV lane data may include timings indicating when HOV lanes are available and minimum passenger requirement in order to user the HOV lanes.

The regional statistics analyzer is responsible for interfacing with the various external systems providing region specific data like traffic information, neighborhood information, infrastructure specific information like bad roads, construction updates, fuel Price, toll charge, public transport information and delays, Available HOV lanes, available call taxi options etc. This data is then used to generate the regional context data and provided to the correlation unit110for specific areas being requested in potential routes.

Further, the regional context data may generate cost context data based on the regional context data. The cost context data may comprise one or more potential routes from the start location to the end location as indicated in the potential travel request. Each of the at least one potential route is associated with a travel time and a travel cost value. In an example, the cost context data is determined by the regional statistical analyzer106by analyzing number of halts, average speed, fuel price, and driving pattern of the user.

In an example, the rule engine108may maintain one or more rules that may be used by the correlation unit110in building travel context data and arriving at related actions. The one or more rules may be stored in a backend system (cloud or hosted) and can be downloaded by the rule engine108whenever the potential travel request is received. The one or more rules may indicate a sequence of steps that should be performed under a predefined scenario. For example, one of the rules may specify that the user may not be able to user the public transport after 11 pm.

Further, the correlation unit110may correlate the potential travel request, the regional context data and the cost context data to obtain the travel context data. The correlation unit110is responsible for executing the workflow defined and correlating the information gathered by the user profiler104and the regional statistical analyzer106.

Once the correlation is done, the navigation module114may determine an optimal route amongst the at least one potential route by applying the one or more rules to the user profile and the travel context data. In an example, the navigation module114may recommend the optimal route to the user as a recommended route on the display unit116.

Further, in an example, the navigation module114may instruct the user to choose the mode of transport, such as car, public transport, and taxi or other means of transport. In case, the user selects the car as the mode of transport, the navigation module114may consider HOV lanes while recommending the optimal route.

Upon determining the optimal route, the navigation module114may dynamically updating the optimal route based on profiles of passengers travelling in the vehicle and High Occupancy Vehicle (HOV) lane data. In an example, to dynamically update the optimal route, the navigation module114may determine presence of the one or more passengers in the vehicle by interacting with the automation engine112. The automation engine112may use additional sensors like occupancy counter, finger print reader, ECG reader, voice recognition, face recognition to identify presence/number of the passengers and provide the same information to the navigation module114. Thereafter, the navigation module114may extracting a passenger profile for each of the passengers from various data sources. The data source could be devices used by the passengers and social media profiles of the passengers. In an example, the passenger profile may comprise preferences, social media profile, and a travel itinerary, age and health condition of the passenger. Thereafter, the navigation module114may update the optimal route to be recommended to the user based on the passenger profile. Example of such scenario would be a family traveling in the morning in a single vehicle, covering different destination like Office, School, and Markets etc. The optimal routes need to be calculated based on historical data, time restrictions and preferences of the passengers.

Further, the navigation module114may consider the HOV lane data to dynamically update the optimal route. In an example, the navigation module114may extract HOV lane usage restrictions (like time) and number of occupants at a given point in time from the HOV lane data to update the optimal route.

Furthermore, the navigation module114is adapted to continuously validate various input factors for updating the context and optimal navigation route. While the trip is in progress, various factors keep changing, such as like traffic conditions, number of passengers, and new notifications/information from different sources. The navigation module114may use such information to update the optimal route. Then, the navigation module114may display the optimal route to the user on the display unit116along with additional information, such as cost associated with the travel, travel time, traffic condition, and weather condition.

FIG. 2illustrates an exemplary method for recommending an optimal route to a user, in accordance with some embodiments of the present disclosure.

The order in which the method200is described is not intended to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the method200or alternative methods. Additionally, individual blocks may be deleted from the method200without departing from the spirit and scope of the subject matter described herein. Furthermore, the method200can be implemented in any suitable hardware, software, firmware, or combination thereof.

With reference toFIG. 2, at block202, a potential travel request is received from a user. The potential travel request may include a start location, an end location, and a time of departure from the start location. In an example, the user profiler104may determine the potential travel request based on user profile. The user profiler104may build the user profile by accessing user preferences, past travel requests, social profiles, a to-do list, calendar invites, and a mode of travel. Once the user profile is determined, the user profiler104may analyze the user profile to determine the potential travel request.

At block204, regional context data is generated by analyzing the potential travel request. In an example, the regional statistical analyzer106may extract at least one region to be covered during the travel based on the potential travel request. Thereafter, the regional statistical analyzer106may determine traffic conditions, number of tolls, modes of transport, the High Occupancy Vehicle (HOV) lane data, public transport details, and fuel price in the at least one region to generate the regional context data.

At block206, cost context data is generated based on the regional context data. The cost context data may comprise potential routes from the start location to the end location. Further, the potential routes are associated with a travel time and a travel cost value. In an example, the regional statistical analyzer106may determine the cost context data based on number of halts, average speed, fuel price, and driving pattern of the user.

At block208, the potential travel request, the regional context data and the cost context data are correlated to obtain travel context data. In an example, the correlation unit110may correlate the potential travel request, the regional context data and the cost context data are correlated to obtain the travel context data.

At block210, an optimal route is determined amongst the at least one potential route by applying one or more rules to the user profile and the travel context data. In an example, the navigation module114may select one of the potential routes as the optimal route based on the one or more rules and the travel context data.

At block212, the optimal route, to be recommended to the user, is dynamically updated based on at least one of presence of one or more passengers in a vehicle and High Occupancy Vehicle (HOV) lane data. In an example, the navigation module114may dynamically update the optimal route based on passenger profiles and the HOV lane data. To update the optimal route based on the passenger profiles, the navigation module114may first determine presence of the one or more passengers in the vehicle. Thereafter, the navigation module114may extract the passenger profile for each of the one or more passengers from one or more data sources. In an example, the passenger profile may comprise preferences, social media profile, and a travel itinerary. Once the passenger profiles are determined, the navigation module114may update the optimal route to be recommended to the user based on the passenger profiles.

Further, to dynamically update the optimal route based on the HOV lane data, the navigation module114may determine a count of the one or more passengers in the vehicle using various sensors. Thereafter, the navigation module114may update the optimal route based on the count and the HOV lane data.

Thus, the system102and the method of the present subject matter leverages various factors, such as user profile, regional context, and HOV lane enforcement while recommending the optimal route to the user. Further, the present subject matter keeps validating external factors, such as traffic information and new passenger to dynamically update the optimal route before recommending it to the user on the display unit116.

Computer System

FIG. 3is a block diagram of an exemplary computer system for implementing embodiments consistent with the present disclosure. Variations of computer system301may be used for implementing various components of the system102presented in this disclosure. Computer system301may comprise a central processing unit (“CPU” or “processor”)302. Processor302may comprise at least one data processor for executing program components for executing user-or system-generated requests. A user may be a person using a device such as those included in this disclosure, or such a device itself. The processor may include specialized processing units such as integrated system (bus) controllers, memory management control units, floating point units, graphics processing units, digital signal processing units, etc. The processor may include a microprocessor, such as AMD Athlon, Duron or Opteron, ARM's application, embedded or secure processors, IBM PowerPC, Intel's Core, Itanium, Xeon, Celeron or other line of processors, etc. The processor302may be implemented using mainframe, distributed processor, multi-core, parallel, grid, or other architectures. Some embodiments may utilize embedded technologies like application-specific integrated circuits (ASICs), digital signal processors (DSPs), Field Programmable Gate Arrays (FPGAs), etc.

Using the I/O interface303, the computer system301may communicate with one or more I/O devices. For example, the input device304may be an antenna, keyboard, mouse, joystick, (infrared) remote control, camera, card reader, fax machine, dongle, biometric reader, microphone, touch screen, touchpad, trackball, sensor (e.g., accelerometer, light sensor, GPS, gyroscope, proximity sensor, or the like), stylus, scanner, storage device, transceiver, video device/source, visors, etc. Output device305may be a printer, fax machine, video display (e.g., cathode ray tube (CRT), liquid crystal display (LCD), light-emitting diode (LED), plasma, or the like), audio speaker, etc. In some embodiments, a transceiver306may be disposed in connection with the processor302. The transceiver may facilitate various types of wireless transmission or reception. For example, the transceiver may include an antenna operatively connected to a transceiver chip (e.g., Texas Instruments WiLink WL1283, Broadcom BCM4750IUB8, lnfineon Technologies X-Gold 618-PMB9800, or the like), providing IEEE 802.11a/b/g/n, Bluetooth, FM, global positioning system (GPS), 2G/3G HSDPA/HSUPA communications, etc.

In some embodiments, the processor302may be disposed in communication with a communication network308via a network interface307. The network interface307may communicate with the communication network308. The network interface may employ connection protocols including, without limitation, direct connect, Ethernet (e.g., twisted pair 10/100/1000 Base T), transmission control protocol/internet protocol (TCP/IP), token ring, IEEE 802.11a/b/g/n/x, etc, The communication network308may include, without limitation, a direct interconnection, local area network (LAN), wide area network (WAN), wireless network (e.g., using Wireless Application Protocol), the Internet, etc. Using the network interface307and the communication network308, the computer system301may communicate with devices310,311, and312. These devices may include, without limitation, personal computer(s), server(s), fax machines, printers, scanners, various mobile devices such as cellular telephones, smartphones (e.g., Apple iPhone, Blackberry, Android-based phones, etc.), tablet computers, eBook readers (Amazon Kindle, Nook, etc.), laptop computers, notebooks, gaming consoles (Microsoft Xbox, Nintendo DS, Sony PlayStation, etc.), or the like. In some embodiments, the computer system301may itself embody one or more of these devices.