Sign In to Follow Application
View All Documents & Correspondence

System And Method For Scalable Multiprocessor Vehicular Task

Abstract: Systems and methods of the present disclosure address the capacity constrained vehicle routing (CVRP) problem that may be applied to a warehouse scenario wherein multi-robot task allocation is required. Conventional methods can solve CVRP instances up to 100 nodes. In the present disclosure, a nearest-neighbor based Clustering And Routing (nCAR) approach is provided that makes the systems and methods of the present disclosure scalable wherein the number of nodes can be in the range of several hundreds to several thousands within an order wave.

Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence

Patent Information

Application #
Filing Date
11 January 2018
Publication Number
29/2019
Publication Type
INA
Invention Field
COMMUNICATION
Status
Email
ip@legasis.in
Parent Application
Patent Number
Legal Status
Grant Date
2024-03-06
Renewal Date

Applicants

Tata Consultancy Services Limited
Nirmal Building, 9th Floor, Nariman Point, Mumbai 400021, Maharashtra, India

Inventors

1. SARKAR, Chayan
Tata Consultancy Services Limited, Building 1B,Ecospace, Innovation Labs, Kolkata - STP, Kolkata - 700160, West Bengal, India
2. PAUL, Himadri Sekhar
Tata Consultancy Services Limited, Building 1B,Ecospace, Innovation Labs, Kolkata - STP, Kolkata - 700160, West Bengal, India
3. PAL, Arindam
Tata Consultancy Services Limited, Building 1B,Ecospace, Innovation Labs, Kolkata - STP, Kolkata - 700160, West Bengal, India
4. MUKHERJEE, Arijit
Tata Consultancy Services Limited, Building 1B,Ecospace, Innovation Labs, Kolkata - STP, Kolkata - 700160, West Bengal, India

Specification

Claims: A processor implemented method (200) comprising: obtaining input parameters comprising number of nodes representative of tasks to be allocated to one or more vehicles, distance between the nodes, demand associated with each of the nodes and maximum capacity of each of the one or more vehicles (202); determining a plurality of clusters of the nodes based on a nearest neighbor based Clustering and Routing (nCAR) approach such that each of the plurality of clusters forms a feasible route for an associated vehicle, wherein a total demand associated with each of the plurality of clusters is within the maximum capacity of the associated vehicle; and the plurality of clusters lead to a lowest total cost, wherein the total cost is representative of a total length travelled by the one or more vehicles to complete all the tasks (204); and determining an optimum route within each of the plurality of clusters using a traveling salesman problem (TSP) approach (206). The processor implemented method of claim 1, wherein the nCAR approach comprises: (i) creating n potential clusters for n number of the nodes, the nodes being initially unassigned to any cluster, the step of creating n potential clusters comprises iteratively performing for each node: initializing demand of an i^th potential cluster to the demand of an i^th node; identifying the i^th node as a current node; iteratively determining a nearest neighbor of the current node based on Euclidean distance therebetween; selecting the nearest neighbor as a cluster member and identifying the nearest neighbor as a new current node if a capacity restriction is satisfied, wherein sum of the demand of the ith potential cluster and the demand of the nearest node representing the total demand is within the maximum capacity of the associated vehicle to form the feasible route; and (ii) selecting a best cluster from the n potential clusters by: computing Euler cycle cost and single node cycle cost associated with nodes of the n potential clusters and assigning summation thereof as total cost for each of the n potential clusters; selecting the potential cluster associated with a lowest total cost as the best cluster; and assigning the nodes of the best cluster to a group T and remaining nodes of the n number of nodes to a group T ¯; (iii) repeating steps (i) and (ii) until the group T ¯ is empty; wherein the best cluster from each iteration constitutes the plurality of clusters that form the feasible route for the associated vehicle. The processor implemented method of claim 1, wherein the plurality of clusters comprises disjoint sets of the nodes except for a depot node representative of a node where a cluster starts and ends. The processor implemented method of claim 1, wherein number of clusters comprising the plurality of clusters determines number of vehicles required to complete all the tasks. A system (100) comprising: one or more data storage devices (102) operatively coupled to one or more hardware processors (104) and configured to store instructions configured for execution by the one or more hardware processors to: obtain input parameters comprising number of nodes representative of tasks to be allocated to one or more vehicles, distance between the nodes, demand associated with each of the nodes and maximum capacity of each of the one or more vehicles; determine a plurality of clusters of the nodes based on a nearest neighbor based Clustering and Routing (nCAR) approach such that each of the plurality of clusters forms a feasible route for an associated vehicle, wherein a total demand associated with each of the plurality of clusters is within the maximum capacity of the associated vehicle; and the plurality of clusters lead to a lowest total cost, wherein the total cost is representative of a total length travelled by the one or more vehicles to complete all the tasks; and determine an optimum route within each of the plurality of clusters using a traveling salesman problem (TSP) approach. The system of claim 5, wherein the one or more hardware processors are further configured to determine a plurality of clusters of the nodes based on the nCAR approach by: (i) creating n potential clusters for n number of the nodes, the nodes being initially unassigned to any cluster, the step of creating n potential clusters comprises iteratively performing for each node: initializing demand of an i^th potential cluster to the demand of an i^th node; identifying the i^th node as a current node; iteratively determining a nearest neighbor of the current node based on Euclidean distance therebetween; selecting the nearest neighbor as a cluster member and identifying the nearest neighbor as a new current node if a capacity restriction is satisfied, wherein sum of the demand of the ith potential cluster and the demand of the nearest node representing the total demand is within the maximum capacity of the associated vehicle to form the feasible route; and (ii) selecting a best cluster from the n potential clusters by: computing Euler cycle cost and single node cycle cost associated with nodes of the n potential clusters and assigning summation thereof as total cost for each of the n potential clusters; selecting the potential cluster associated with a lowest total cost as the best cluster; and assigning the nodes of the best cluster to a group T and remaining nodes of the n number of nodes to a group T ¯; (iii) repeating steps (i) and (ii) until the group T ¯ is empty; wherein the best cluster from each iteration constitutes the plurality of clusters that form the feasible route for the associated vehicle. The system of claim 5, wherein the plurality of clusters comprises disjoint sets of the nodes except for a depot node representative of a node where a cluster starts and ends. The system of claim 5, wherein number of clusters comprising the plurality of clusters determines number of vehicles required to complete all the tasks. , Description:FORM 2 THE PATENTS ACT, 1970 (39 of 1970) & THE PATENT RULES, 2003 COMPLETE SPECIFICATION (See Section 10 and Rule 13) Title of invention: SYSTEMS AND METHODS FOR SCALABLE MULTI-VEHICLE TASK ALLOCATION Applicant: Tata Consultancy Services Limited A company Incorporated in India under the Companies Act, 1956 Having address: Nirmal Building, 9th Floor, Nariman Point, Mumbai 400021, Maharashtra, India The following specification particularly describes the invention and the manner in which it is to be performed. TECHNICAL FIELD The disclosure herein generally relates to a capacity constrained vehicle routing problem (CVRP), and more particularly relates to systems and methods for scalable multi-vehicle task allocation. BACKGROUND In modern warehouses, robots are generally employed along with humans to perform tasks that are less productive and unsafe for humans. For instance, the tasks may involve robots fetching outgoing objects from their respective storage racks and bringing them to the packaging dock. This requires a careful task allocation along with route planning such that the total path traveled (cost) by all the robots to complete all the tasks is minimized. The number of tasks that can be performed in a single run (part of the same route) depends on the maximum capacity of the robot and the combined weight of the objects on that route. This task allocation problem may be mapped to the capacity-constrained vehicle routing problem (CVRP), which is a nondeterministic polynomial time (NP) hard problem. Though there exists a number of methods that provide a near-optimal solution to the CVRP instance, they do not scale well with the number of nodes (tasks). SUMMARY Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. In an aspect, there is provided a processor implemented method comprising: obtaining input parameters comprising number of nodes representative of tasks to be allocated to one or more vehicles, distance between the nodes, demand associated with each of the nodes and maximum capacity of each of the one or more vehicles; determining a plurality of clusters of the nodes based on a nearest neighbor based Clustering and Routing (nCAR) approach such that each of the plurality of clusters forms a feasible route for an associated vehicle, wherein a total demand associated with each of the plurality of clusters is within the maximum capacity of the associated vehicle; and the plurality of clusters lead to a lowest total cost, wherein the total cost is representative of a total length travelled by the one or more vehicles to complete all the tasks; and determining an optimum route within each of the plurality of clusters using a traveling salesman problem (TSP) approach. In another aspect, there is provided a system comprising: one or more data storage devices operatively coupled to the one or more processors and configured to store instructions configured for execution by the one or more processors to: obtain input parameters comprising number of nodes representative of tasks to be allocated to one or more vehicles, distance between the nodes, demand associated with each of the nodes and maximum capacity of each of the one or more vehicles; determine a plurality of clusters of the nodes based on a nearest neighbor based Clustering and Routing (nCAR) approach such that each of the plurality of clusters forms a feasible route for an associated vehicle, wherein a total demand associated with each of the plurality of clusters is within the maximum capacity of the associated vehicle; and the plurality of clusters lead to a lowest total cost, wherein the total cost is representative of a total length travelled by the one or more vehicles to complete all the tasks; and determine an optimum route within each of the plurality of clusters using a traveling salesman problem (TSP) approach. In yet another aspect, there is provided a computer program product comprising a non-transitory computer readable medium having a computer readable program embodied therein, wherein the computer readable program, when executed on a computing device, causes the computing device to: obtain input parameters comprising number of nodes representative of tasks to be allocated to one or more vehicles, distance between the nodes, demand associated with each of the nodes and maximum capacity of each of the one or more vehicles; determine a plurality of clusters of the nodes based on nearest neighbor based Clustering and Routing (nCAR) approach such that each of the plurality of clusters forms a feasible route for an associated vehicle, wherein a total demand associated with each of the plurality of clusters is within the maximum capacity of the associated vehicle; and the plurality of clusters lead to a lowest total cost, wherein the total cost is representative of a total length travelled by the one or more vehicles to complete all the tasks; and determine an optimum route within each of the plurality of clusters using a traveling salesman problem (TSP) approach. In an embodiment of the present disclosure, the one or more hardware processors are further configured to determine a plurality of clusters of the nodes based on the nCAR approach by: (i) creating n potential clusters for n number of the nodes, the nodes being initially unassigned to any cluster, the step of creating n potential clusters comprises iteratively performing for each node: initializing demand of an i^th potential cluster to the demand of an i^th node; identifying the i^th node as a current node; iteratively determining a nearest neighbor of the current node based on Euclidean distance therebetween; selecting the nearest neighbor as a cluster member and identifying the nearest neighbor as a new current node if a capacity restriction is satisfied, wherein sum of the demand of the ith potential cluster and the demand of the nearest node representing the total demand is within the maximum capacity of the associated vehicle to form the feasible route; and (ii) selecting a best cluster from the n potential clusters by: computing Euler cycle cost and single node cycle cost associated with nodes of the n potential clusters and assigning summation thereof as total cost for each of the n potential clusters; selecting the potential cluster associated with a lowest total cost as the best cluster; and assigning the nodes of the best cluster to a group T and remaining nodes of the n number of nodes to a group T ¯; (iii) repeating steps (i) and (ii) until the group T ¯ is empty; wherein the best cluster from each iteration constitutes the plurality of clusters that form the feasible route for the associated vehicle. In an embodiment of the present disclosure, the plurality of clusters comprises disjoint sets of the nodes except for a depot node representative of a node where a cluster starts and ends. In an embodiment of the present disclosure, number of clusters comprising the plurality of clusters determines number of vehicles required to complete all the tasks. It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the embodiments of the present disclosure, as claimed. BRIEF DESCRIPTION OF THE DRAWINGS The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed principles. FIG.1 illustrates a schematic representation of a single task completion on a single run (ST-SR) versus more than one task completion on a single run (MT-SR) as known in the art. FIG.2 illustrates an exemplary block diagram of a system for scalable multi-vehicle task allocation, in accordance with an embodiment of the present disclosure. FIG.3 is an exemplary flow diagram illustrating a computer implemented method for scalable multi-vehicle task allocation, in accordance with an embodiment of the present disclosure. FIG.4 provides a graphical representation of cost ratio of Google™ optimization tools (OR- Tools) and the method of the present disclosure using P-dataset of the Capacitated Vehicle Routing Problem Library (CVRPLIB). FIG.5 provides a graphical representation of the execution time of Google™ optimization tools (OR- Tools) and the method of the present disclosure using P-dataset of the Capacitated Vehicle Routing Problem Library (CVRPLIB). FIG.6 provides a graphical representation of the execution time of Google™ optimization tools (OR- Tools) and the method of the present disclosure using X-dataset provided by Uchoa et al. FIG.7 provides a cost comparison between Google™ optimization tools (OR- Tools) and the method of the present disclosure for a large number of nodes. FIG.8 provides a performance comparison in terms of execution time between Google™ optimization tools (OR- Tools) and the method of the present disclosure for a large number of nodes. FIG.9 provides a performance comparison in terms of number of routes between Google™ optimization tools (OR- Tools) and the method of the present disclosure for a large number of nodes. It should be appreciated by those skilled in the art that any block diagram herein represent conceptual views of illustrative systems embodying the principles of the present subject matter. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computing device or processor, whether or not such computing device or processor is explicitly shown. 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. It is intended that the following detailed description be considered as exemplary only, with the true scope and spirit being indicated by the following claims. In general, automation using a group of mobile robots constitutes two major steps viz., task allocation and task execution. The goal of task allocation is to ensure that the overall cost of executing all the tasks is minimized, while redundant robot resources are not allocated to complete a task. On the other hand, task execution ensures that the tasks are executed correctly and safely according to the assignment. The present disclosure focuses on task allocation. In a warehouse scenario, the task of a robot is defined as moving to a location of a particular object, fetching the object from a storage rack, and returning to the original location (packaging dock). Though a robot almost never fetches multiple objects from the racks simultaneously, it can fetch more than one object on a single run, before returning back to the dock. This reduces the overall travel time as compared to fetching one object on a single run. FIG.1 illustrates a schematic representation of a single task completion on a single run (ST-SR) versus more than one task (multiple tasks) completion on a single run (MT-SR) as known in the art. Obviously, the total time required to fetch all the required objects is smaller in the case of MT-SR if the objects in close proximity are fetched on a single run. The ST-SR is a special constrained version of the MT-SR problem. The associated problem in MT-SR case is to group tasks, optimally, to be given to a robot, given that each of the robots has a certain (fixed) carrying capacity. The present disclosure is directed to a multi robot task allocation problem that is reduced to a capacity constrained vehicle routing (CVRP) problem, where each robot is constrained by its maximum weight carrying capacity. The intent is to assign tasks to the robots such that overall time to bring the items to the packing dock can be minimized. Since CVRP is a known nondeterministic polynomial time (NP) hard problem, Conventional exact and heuristic methods for CVRP do not scale well with the number of nodes (tasks). In applications like the warehouse scenario, the number of nodes may be large and vary significantly (from couple of hundreds to thousands) as opposed to smaller number of nodes in typical CVRP instances (generally up to a hundred). Thus, the prevalent methods become impractical. In the context of the present disclosure, the expressions ‘vehicle’ and ‘robot’ may be used interchangeably. Although further description of the present disclosure is directed to a warehouse scenario, it may be noted that the described application is non-limiting and systems and methods of the present disclosure may be applied in any domain, where the CVRP instances particularly involve a large number of tasks (nodes) to be allocated such as courier service, car pool service, product delivery service, and the like. In a warehouse, an item is scheduled to be dispatched when a customer places an order for it. Usually a warehouse is spread across a very large area, and items are also stored in racks across a vast field. The task for a robot is to fetch the items from storage racks to the packaging dock. In the present disclosure, it is assumed that the robots are homogeneous and each one has a fixed maximum weight carrying capacity. It is also assumed that the tasks are homogeneous in nature, but they differ based on the storage location and weight of the item. In general, tasks are handled as a wave, where a wave contains couple hundreds to thousands tasks. Once the tasks are completed, the next wave, which accumulates during the execution of the previous wave, is picked for execution. The present disclosure provides a heuristic method such that the cost of fetching all the ordered items may be minimized. In the context of the present disclosure, the cost refers to the total path length traveled by all the robots to complete all the tasks. A robot always starts from and comes back to the packaging dock of the warehouse. On a single run, a robot can fetch multiple items, i.e., completing multiple tasks, provided the total demand (weight) of all the tasks is within the capacity of the robot. Thus, it can be classified as a multi-task robot and single-robot task (MT-SR) assignment problem, wherein one robot performs multiple tasks simultaneously and to complete a task one robot is needed. The problem can be reduced to the classical CVRP problem, where a number of vehicles start and end their journey at a depot. On their journey, they service a number of customers, where the total demand of all the customers on a single journey must be within the capacity limit of the robots. The goal is to find an optimal route for each of the robots such that the total cost of the all the journeys made by the fleet of robots is minimized and all the customers are serviced by exactly one robot. As CVRP is known to be NP hard, the MT-SR assignment problem is also an NP-hard problem. The mathematical formulation of the technical problem may be presented as given hereinafter. Let G=(V,E) be an undirected, complete graph. The number of vertices in the graph is |V|=n+1. The vertices may be denoted as V={v_0,v_1,….,v_n }, wherein vertex v_0corresponds to the depot and other vertices V'=V\{v_0 } correspond to n sites. Let V_i={v_i,0=i=n}. The number of vertices may be denoted as E, wherein each e?E has a cost c_e>0. This is the cost of traveling the edge e. For each vertex v_i?V', there is an associated demand d_i>0, which has to be satisfied. Let k be the number of robots available at the depot and let C be the capacity of each robot. Without loss of generality, it is assumed that the maximum demand of any vertex is at most the capacity of each robot, i.e., d_i

Documents

Orders

Section Controller Decision Date

Application Documents

# Name Date
1 201821001295-IntimationOfGrant06-03-2024.pdf 2024-03-06
1 201821001295-STATEMENT OF UNDERTAKING (FORM 3) [11-01-2018(online)].pdf 2018-01-11
2 201821001295-PatentCertificate06-03-2024.pdf 2024-03-06
2 201821001295-REQUEST FOR EXAMINATION (FORM-18) [11-01-2018(online)].pdf 2018-01-11
3 201821001295-Written submissions and relevant documents [30-10-2023(online)].pdf 2023-10-30
3 201821001295-FORM 18 [11-01-2018(online)].pdf 2018-01-11
4 201821001295-FORM 1 [11-01-2018(online)].pdf 2018-01-11
4 201821001295-Correspondence to notify the Controller [09-10-2023(online)].pdf 2023-10-09
5 201821001295-FORM-26 [09-10-2023(online)]-1.pdf 2023-10-09
5 201821001295-FIGURE OF ABSTRACT [11-01-2018(online)].jpg 2018-01-11
6 201821001295-FORM-26 [09-10-2023(online)].pdf 2023-10-09
6 201821001295-DRAWINGS [11-01-2018(online)].pdf 2018-01-11
7 201821001295-US(14)-HearingNotice-(HearingDate-17-10-2023).pdf 2023-09-05
7 201821001295-COMPLETE SPECIFICATION [11-01-2018(online)].pdf 2018-01-11
8 201821001295-Proof of Right (MANDATORY) [05-02-2018(online)].pdf 2018-02-05
8 201821001295-PETITION UNDER RULE 137 [03-12-2020(online)].pdf 2020-12-03
9 201821001295-FORM-26 [26-02-2018(online)].pdf 2018-02-26
9 201821001295-RELEVANT DOCUMENTS [03-12-2020(online)].pdf 2020-12-03
10 201821001295-CLAIMS [29-11-2020(online)].pdf 2020-11-29
10 Abstract1.jpg 2018-08-11
11 201821001295-COMPLETE SPECIFICATION [29-11-2020(online)].pdf 2020-11-29
11 201821001295-ORIGINAL UNDER RULE 6 (1A)-FORM 26-010318.pdf 2018-08-11
12 201821001295-FER_SER_REPLY [29-11-2020(online)].pdf 2020-11-29
12 201821001295-ORIGINAL UNDER RULE 6 (1A)-080218.pdf 2018-08-11
13 201821001295-OTHERS [29-11-2020(online)].pdf 2020-11-29
13 201821001295-REQUEST FOR CERTIFIED COPY [24-08-2018(online)].pdf 2018-08-24
14 201821001295-CORRESPONDENCE(IPO)-(CERTIFIED COPY)-(28-8-2018).pdf 2018-08-29
14 201821001295-FER.pdf 2020-05-29
15 201821001295-FORM 3 [11-12-2018(online)].pdf 2018-12-11
16 201821001295-CORRESPONDENCE(IPO)-(CERTIFIED COPY)-(28-8-2018).pdf 2018-08-29
16 201821001295-FER.pdf 2020-05-29
17 201821001295-REQUEST FOR CERTIFIED COPY [24-08-2018(online)].pdf 2018-08-24
17 201821001295-OTHERS [29-11-2020(online)].pdf 2020-11-29
18 201821001295-ORIGINAL UNDER RULE 6 (1A)-080218.pdf 2018-08-11
18 201821001295-FER_SER_REPLY [29-11-2020(online)].pdf 2020-11-29
19 201821001295-COMPLETE SPECIFICATION [29-11-2020(online)].pdf 2020-11-29
19 201821001295-ORIGINAL UNDER RULE 6 (1A)-FORM 26-010318.pdf 2018-08-11
20 201821001295-CLAIMS [29-11-2020(online)].pdf 2020-11-29
20 Abstract1.jpg 2018-08-11
21 201821001295-FORM-26 [26-02-2018(online)].pdf 2018-02-26
21 201821001295-RELEVANT DOCUMENTS [03-12-2020(online)].pdf 2020-12-03
22 201821001295-PETITION UNDER RULE 137 [03-12-2020(online)].pdf 2020-12-03
22 201821001295-Proof of Right (MANDATORY) [05-02-2018(online)].pdf 2018-02-05
23 201821001295-COMPLETE SPECIFICATION [11-01-2018(online)].pdf 2018-01-11
23 201821001295-US(14)-HearingNotice-(HearingDate-17-10-2023).pdf 2023-09-05
24 201821001295-DRAWINGS [11-01-2018(online)].pdf 2018-01-11
24 201821001295-FORM-26 [09-10-2023(online)].pdf 2023-10-09
25 201821001295-FORM-26 [09-10-2023(online)]-1.pdf 2023-10-09
25 201821001295-FIGURE OF ABSTRACT [11-01-2018(online)].jpg 2018-01-11
26 201821001295-FORM 1 [11-01-2018(online)].pdf 2018-01-11
26 201821001295-Correspondence to notify the Controller [09-10-2023(online)].pdf 2023-10-09
27 201821001295-Written submissions and relevant documents [30-10-2023(online)].pdf 2023-10-30
27 201821001295-FORM 18 [11-01-2018(online)].pdf 2018-01-11
28 201821001295-REQUEST FOR EXAMINATION (FORM-18) [11-01-2018(online)].pdf 2018-01-11
28 201821001295-PatentCertificate06-03-2024.pdf 2024-03-06
29 201821001295-STATEMENT OF UNDERTAKING (FORM 3) [11-01-2018(online)].pdf 2018-01-11
29 201821001295-IntimationOfGrant06-03-2024.pdf 2024-03-06

Search Strategy

1 SEARCH201821001295_28-02-2020.pdf

ERegister / Renewals

3rd: 06 Jun 2024

From 11/01/2020 - To 11/01/2021

4th: 06 Jun 2024

From 11/01/2021 - To 11/01/2022

5th: 06 Jun 2024

From 11/01/2022 - To 11/01/2023

6th: 06 Jun 2024

From 11/01/2023 - To 11/01/2024

7th: 06 Jun 2024

From 11/01/2024 - To 11/01/2025

8th: 11 Jan 2025

From 11/01/2025 - To 11/01/2026