Method and system for optimally allocating warehouse procurement tasks to distributed robotic agents

Patent metadata

Field	Value
Publication number	US-10235642-B2
Application number	US-201715827513-A
Country	US
Kind code	B2
Filing date	Nov 30, 2017
Priority date	Aug 11, 2017
Publication date	Mar 19, 2019
Grant date	Mar 19, 2019

Abstract

This disclosure relates generally to autonomous devices, and more particularly to method and system to optimally allocate warehouse procurement tasks to distributed autonomous devices. The method includes obtaining, at a coordinating agent, a global task associated with the warehouse and information associated with the robotic agents. The information includes a count and status of the robotic agents. The global task is profiled to obtain a set of sub-tasks and constraints associated with the set of sub-tasks are identified. The constraints include utilization constraint and/or pricing constraints. A distributed, decentralized optimal task allocation is performed amongst the robotic agents based on constraints to obtain optimal performance of robotic agents. The distributed optimal task allocation includes performing primal or dual decomposition of the set of sub-tasks by each robotic agent and updating corresponding primal/dual variables by the coordinating agent when the optimization is performed based on utilization constraint and pricing constraints, respectively.

First claim

What is claimed is:

1. A processor-implemented method for optimally allocating warehouse procurement tasks to distributed robotic agents, the method comprising:
obtaining, at a coordinating agent of a plurality of robotic agents, a global task associated with the warehouse and an information associated with the plurality of robotic agents available for the global task, via one or more hardware processors, said information comprising a count and status of the plurality of robotic agents;
profiling the global task to obtain a set of sub-tasks and identifying one or more constraints associated with the set of sub-tasks, via the one or more hardware processors, a constraint of the one or more constraints comprises one of a utilization constraint and one or more pricing constraints; and
performing, via the one or more hardware processors, distributed, decentralized optimal task allocation amongst the plurality of robotic agents based at least on the one or more constraints, to obtain optimal performance of the plurality of robotic agents in accomplishment of the global task, the distributed optimal task allocation comprises:
performing a primal decomposition of the set of sub-tasks by each robotic agent of the plurality or robotic agents and updating a set of corresponding primal variables by the coordinating agent when the optimization is performed based on the utilization constraint, and
performing a dual decomposition of the set of sub-tasks by each robotic agent of the plurality or robotic agents updating a set of corresponding dual variables by the coordinating agent, when the optimization is performed based on the one or more pricing constraints.

2. The method of claim 1 , wherein the warehouse deploys a plurality of autonomous agents, the plurality of autonomous agents include:
at least one server agent to allocate the global task, and
the plurality of robotic agents comprising a plurality of delivery agents and a plurality of picker agents for performing the global task, the plurality of delivery agents further comprising a set of coordinating agents for coordination among remaining robotic agents of the plurality of delivery agents to allocate the task to the delivery agents.

3. The method of claim 2 , wherein the at least one server agent is capable of:
selecting a set of tasks from a task queue, each task of the set of tasks corresponds to one of a set of items to be procured from and dropped to a location in the warehouse, wherein each item among the set of items is associated with corresponding item dimensions, weight and location coordinates;
creating an aggregated list of the set of items associated with each task;
categorizing the aggregated list into a set of item lists based on the item dimensions, weight and the location coordinates of each item; and
forwarding a set of subtasks associated with the set of item lists to the plurality of delivery agents, wherein each subtask among the set of subtasks corresponds to procuring/dropping items from an item list from the set of item list.

4. The method of claim 1 , wherein the utilization constraint comprises maximization of resource utilization of the plurality of robotic agents.

5. The method of claim 1 , wherein the one or more pricing constraints comprises minimization of latency and minimization of energy usage.

6. The method of claim 1 , wherein the coordinating agent is configured to provide fault tolerance by redistributing an incomplete task from the global task, discontinued due to a faulty delivery agent, to the remaining delivery agents from the set of delivery agents.

7. A system for optimally allocating warehouse procurement tasks to distributed robotic agents, the system comprising:
one or more memories storing instructions; and
one or more hardware processors coupled to the one or more memories, wherein said one or more hardware processors are configured by said instructions to:
obtain, at a coordinating agent of a plurality of robotic agents, a global task associated with the warehouse and an information associated with the plurality of robotic agents available for the global task, said information comprising a count and status of the plurality of robotic agents;
profile the global task to obtain a set of sub-tasks and identifying one or more constraints associated with the set of sub-tasks, a constraint of the one or more constraints comprises one of a utilization constraint and one or more pricing constraints; and
perform distributed, decentralized optimal task allocation amongst the plurality of robotic agents based at least on the one or more constraints, to obtain optimal performance of the plurality of robotic agents in accomplishment of the global task, the distributed optimal task allocation comprises:
perform a primal decomposition of the set of sub-tasks by each robotic agent of the plurality or robotic agents and updating a set of corresponding primal variables by the coordinating agent when the optimization is performed based on a utilization constraint, and
perform a dual decomposition of the set of sub-tasks by each robotic agent of the plurality or robotic agents and updating a set of corresponding dual variables by the coordinating agent, when the optimization is performed based on one or more pricing constraints.

8. The system of claim 7 , wherein the warehouse deploys a plurality of autonomous agents, the plurality of autonomous agents include:
at least one server agent to allocate the global task, and
the plurality of robotic agents comprising a plurality of delivery agents and a plurality of picker agents for performing the global task, the plurality of delivery agents further comprising a set of coordinating agents for coordination among remaining robotic agents of the plurality of delivery agents to allocate the task to the delivery agents.

9. The system of claim 8 , wherein the at least one server agent is capable of:
selecting a set of tasks from a task queue, each task of the set of tasks corresponds to one of a set of items to be procured from/and dropped to a location in the warehouse, wherein each item among the set of items is associated with corresponding item dimensions, weight and location coordinates;
creating an aggregated list of the set of items associated with each task;
categorizing the aggregated list into a set of item lists based on the item dimensions, weight and the location coordinates of each item; and
forwarding a set of subtasks associated with the set of item lists to the plurality of delivery agents, wherein each subtask among the set of subtasks corresponds to procuring/dropping items from an item list from the set of item list.

10. The system of claim 7 , wherein the utilization constraint comprises maximization of resource utilization of the plurality of robotic agents.

11. The system of claim 7 , wherein the one or more pricing constraints comprises minimization of latency and minimization of energy usage.

12. The method of claim 7 , wherein the coordinating agent is configured to provide fault tolerance by redistributing an incomplete task from the global task, discontinued due to a faulty delivery agent, to the remaining delivery agents from the set of delivery agents.

13. A non-transitory computer-readable medium having embodied thereon a computer program for executing a method for optimally allocating warehouse procurement tasks to distributed robotic agents, the method comprising:
obtaining, at a coordinating agent of a plurality of robotic agents, a global task associated with the warehouse and an information associated with the plurality of robotic agents available for the global task, via one or mor

Assignees

• Tata Consultancy Services Ltd

Inventors

• Kattepur Ajay
• Rath Hemant Kumar
• Simha Anantha
• Mukherjee Arijit

Classifications

• G05B19/41895

  using automatic guided vehicles [AGV] (control of position or course of AGV's G05D1/00) · CPC title

• G05B2219/39146

  Swarm, multiagent, distributed multitask fusion, cooperation multi robots · CPC title

• G05B2219/39167

  Resources scheduling and balancing · CPC title

• G06Q10/04 Primary

  Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202) · CPC title

• G05B19/41865

  characterised by job scheduling, process planning, material flow · CPC title