Systems and methods for dynamic task scheduling and rescheduling using heterogeneous multi-agent fleet
This disclosure relates generally to system and methods for dynamic scheduling and rescheduling using heterogeneous multi-agent fleet. The embodiments of present disclosure herein address unresolved problem of task allocation using a single solution which is not sufficient for handling various scenarios of multi-agent task allocation problems. For instance, the task allocation becomes more challenging in a scenario where each task has a deadline associated with it and execution time of the tasks cannot be pre-computed as they are dependent on previous tasks. The method of present disclosure provides a scalable solution for dynamic scheduling and rescheduling that handles tasks with multiple pickup and drop locations and dynamic execution time using the agents with heterogeneous speed in a more efficient manner, reducing indirect operating costs and increasing revenue potential while minimizing additional penalty due to run time delays that an agent may encounter.
1. A processor-implemented method, comprising:
receiving, via one or more hardware processors, a set of tasks to be allocated to a multi-agent fleet comprising a plurality of heterogeneous agents, wherein each task from the set of tasks is characterized by an execution time of the task being performed by an agent from the plurality of heterogeneous agents, a corresponding predefined deadline and a corresponding predefined penalty for missing the corresponding predefined deadline, and wherein the execution time of the task is a function of one or more task specific parameters, one or more static agent specific parameters and one or more dynamic agent specific parameters;
obtaining, via the one or more hardware processors, a first task list by sorting the set of tasks based on the corresponding predefined deadline and the corresponding predefined penalty for missing the corresponding predefined deadline;
selecting, via the one or more hardware processors, a first task from the first task list such that the corresponding predefined penalty of the first task is maximum in comparison to the corresponding predefined penalties of one or more remaining tasks in the first task list to perform one of:
(i) iterating the first task on the plurality of heterogeneous agents to identify a first set of agents such that the first task is schedulable on the first set of agents without missing the corresponding predefined deadline when executed from a current location to a second location through a first location, and
(ii) selecting an agent from the first set of agents to allocate the first task based on a minimum slack value based selection criterion, wherein the slack value is a function of an agent speed and indicates a gap between the corresponding predefined deadline of the first task and an end time of each of a plurality of tasks being executed by the selected agent; or
(a) adding the first task to a second task list when the first task is non-schedulable on the plurality of heterogeneous agents without missing the corresponding predefined deadline, wherein the second task list is a subset of the first task list;
iteratively performing previous step for each task in the first task list to obtain a first task allocation sequence;
scheduling, via the one or more hardware processors, each task from the second task list to the plurality of heterogeneous agents such that a minimum penalty out of the corresponding predefined penalties is incurred and a second task allocation sequence is obtained;
detecting, via the one or more hardware processors, a delay in execution of a plurality of tasks to determine a status indicative of missing the corresponding predefined deadline or not missing the corresponding predefined deadline by corresponding agents during execution of the plurality of tasks; wherein when there are no additional deadline misses, dynamic task scheduling process proceeds without changes; and
dynamically creating, via the one or more hardware processors, based on the status indicative of missing the corresponding predefined deadline, a new schedule by performing one of:
(a) determining whether each of the plurality of tasks being executed by the corresponding agents missing the corresponding predefined deadline is reschedulable at a position on the second task allocation sequence that is different from a previous position of the corresponding agents on the second task allocation sequence while incurring lesser penalty in comparison to the corresponding predefined penalty, and
swapping each of the plurality of tasks being executed by the corresponding agents missing the corresponding predefined deadline with a second task scheduled on the corresponding agents; or
(i) determining whether each of the plurality of tasks being executed by the corresponding agents missing the corresponding predefined deadline is reschedulable on an agent from the plurality of heterogeneous agents that is different from the corresponding agent while incurring lesser penalty in comparison to the corresponding predefined penalty,
allocating each of the plurality of tasks to the agent from the plurality of heterogeneous agents that is different from the corresponding agent,
determining when the delay is detected on an agent and a task is identified as missing the corresponding predefined deadline;
calculating a penalty for missing the deadline;
checking possibility of switching task with another task on the agent such that penalty incurred is less than the corresponding predefined penalty ; and
switching tasks and creating the new schedule, when there exists possibility of switching task with another task; or
mapping the task identified as missing to a new agent and the new schedule is created.
2. The method of claim 1 , wherein the one or more task specific parameters comprising coordinates of the first location and the second location.
3. The method of claim 1 , wherein the first location is indicative of a pickup location and the second location is indicative of a drop location.
4. The method of claim 1 , wherein the one or more static agent specific parameters comprising agent speed without any payload, an agent speed with payload, an actuation time to a perform a first subtask, and an actuation time to perform a second subtask.
5. The method of claim 1 , wherein the one or more dynamic agent specific parameters comprising the current location and a residual energy of the agent.
6. A system, comprising:
a memory storing instructions;
one or more communication interfaces; and
one or more hardware processors coupled to the memory via the one or more communication interfaces, wherein the one or more hardware processors are configured by the instructions to:
receive, a set of tasks to be allocated to a multi-agent fleet comprising a plurality of heterogeneous agents, wherein each task from the set of tasks is characterized by an execution time of the task being performed by an agent from the plurality of heterogeneous agents, a corresponding predefined deadline and a corresponding predefined penalty for missing the corresponding predefined deadline, and wherein the execution time of the task is a function of one or more task specific parameters, one or more static agent specific parameters and one or more dynamic agent specific parameters;
obtain a first task list by sorting the set of tasks based on the corresponding predefined deadline and the corresponding predefined penalty for missing the corresponding predefined deadline;
select a first task from the first task list such that the corresponding predefined penalty of the first task is maximum in comparison to the corresponding predefined penalties of one or more remaining tasks in the first task list to perform one of:
(i) iterating the first task on the plurality of heterogeneous agents to identify a first set of agents such that the first task is schedulable on the first set of agents without missing the corresponding predefined deadline when executed from a current location to a second location through a first location, and
(ii) selecting an agent from the first set of agents to allocate the first task based on a minimum slack value based selection criterion, wherein the slack value is a function of an agent speed and indicates a gap between the corresponding predefined deadline of the first task and an end time of each of a plurality of tasks being executed by the selected agent; or
(a) adding the first task to a second task list when the first task is non-schedulable on the plurality of heterogeneous agents without missing the corresponding predefined deadline, wherein the second task list is a subset of the first task list;
iteratively perform previous step for each task in the first task list to obtain a first task allocation sequence;
schedule each task from the second task list to the plurality of heterogeneous agents such that a minimum penalty out of the corresponding predefined penalties is incurred and a second task allocation sequence is obtained;
detect a delay in execution of a plurality of tasks to determine a status indicative of missing the corresponding predefined deadline or not missing the corresponding predefined deadline by corresponding agents during execution of the plurality of tasks, wherein when there are no additional deadline misses, dynamic task scheduling process proceeds without changes; and
dynamically create, based on the status indicative of missing the corresponding predefined deadline, a new schedule by performing one of:
(a) determining whether each of the plurality of tasks being executed by the corresponding agents missing the corresponding predefined deadline is reschedulable at a position on the second task allocation sequence that is different from a previous position of the corresponding agents on the second task allocation sequence while incurring lesser penalty in comparison to the corresponding predefined penalty, and
swapping each of the plurality of tasks being executed by the corresponding agents missing the corresponding predefined deadline with a second task scheduled on the corresponding agents; or
(i) determining whether each of the plurality of tasks being executed by the corresponding agents missing the corresponding predefined deadline is reschedulable on an agent from the plurality of heterogeneous agents that is different from the corresponding agent while incurring less penalty in comparison to the corresponding predefined penalty,
allocating each of the plurality of tasks to the agent from the plurality of heterogeneous agents that is different from the corresponding agent,
determining when the delay is detected on an agent and a task is identified as missing the corresponding predefined deadline;
calculating a penalty for missing the deadline;
checking possibility of switching task with another task on the agent such that penalty incurred is less than the corresponding predefined penalty; and
switching tasks and creating the new schedule, when there exists possibility of switching task with another task; or
mapping the task identified as missing to a new agent and the new schedule is created.
7. The system of claim 6 , wherein the one or more task specific parameters comprising coordinates of the first location and the second location.
8. The system of claim 6 , wherein the first location is indicative of a pickup location and the second location is indicative of a drop location.
9. The system of claim 6 , wherein the one or more static agent specific parameters comprising agent speed without any payload, an agent speed with payload, an actuation time to a perform a first subtask, and an actuation time to perform a second subtask.
10. The system of claim 6 , wherein the one or more dynamic agent specific parameters comprising the current location and a residual energy of the agent.
11. One or more non-transitory computer readable mediums comprising one or more instructions which when executed by one or more hardware processors cause:
receiving, via one or more hardware processors, a set of tasks to be allocated to a multi-agent fleet comprising a plurality of heterogeneous agents, wherein each task from the set of tasks is characterized by an execution time of the task being performed by an agent from the plurality of heterogeneous agents, a corresponding predefined deadline and a corresponding predefined penalty for missing the corresponding predefined deadline, and wherein the execution time of the task is a function of one or more task specific parameters, one or more static agent specific parameters and one or more dynamic agent specific parameters;
obtaining, via the one or more hardware processors, a first task list by sorting the set of tasks based on the corresponding predefined deadline and the corresponding predefined penalty for missing the corresponding predefined deadline;
selecting, via the one or more hardware processors, a first task from the first task list such that the corresponding predefined penalty of the first task is maximum in comparison to the corresponding predefined penalties of one or more remaining tasks in the first task list to perform one of:
(i) iterating the first task on the plurality of heterogeneous agents to identify a first set of agents such that the first task is schedulable on the first set of agents without missing the corresponding predefined deadline when executed from a current location to a second location through a first location, and
(ii) selecting an agent from the first set of agents to allocate the first task based on a minimum slack value based selection criterion, wherein the slack value is a function of an agent speed and indicates a gap between the corresponding predefined deadline of the first task and an end time of each of a plurality of tasks being executed by the selected agent; or
(a) adding the first task to a second task list when the first task is non-schedulable on the plurality of heterogeneous agents without missing the corresponding predefined deadline, wherein the second task list is a subset of the first task list;
iteratively performing previous step for each task in the first task list to obtain a first task allocation sequence;
scheduling, via the one or more hardware processors, each task from the second task list to the plurality of heterogeneous agents such that a minimum penalty out of the corresponding predefined penalties is incurred and a second task allocation sequence is obtained;
detecting, via the one or more hardware processors, a delay in execution of a plurality of tasks to determine a status indicative of missing the corresponding predefined deadline or not missing the corresponding predefined deadline by corresponding agents during execution of the plurality of tasks, wherein when there are no additional deadline misses, dynamic task scheduling process proceeds without changes; and
dynamically creating, via the one or more hardware processors, based on the status indicative of missing the corresponding predefined deadline, a new schedule by performing one of:
(a) determining whether each of the plurality of tasks being executed by the corresponding agents missing the corresponding predefined deadline is reschedulable at a position on the second task allocation sequence that is different from a previous position of the corresponding agents on the second task allocation sequence while incurring lesser penalty in comparison to the corresponding predefined penalty, and
swapping each of the plurality of tasks being executed by the corresponding agents missing the corresponding predefined deadline with a second task scheduled on the corresponding agents; or
(i) determining whether each of the plurality of tasks being executed by the corresponding agents missing the corresponding predefined deadline is reschedulable on an agent from the plurality of heterogeneous agents that is different from the corresponding agent while incurring lesser penalty in comparison to the corresponding predefined penalty,
allocating each of the plurality of tasks to the agent from the plurality of heterogeneous agents that is different from the corresponding agent,
determining when the delay is detected on an agent and a task is identified as missing the corresponding predefined deadline;
calculating a penalty for missing the deadline;
checking possibility of switching task with another task on the agent such that penalty incurred is less than the corresponding predefined penalty; and
switching tasks and creating the new schedule, when there exists possibility of switching task with another task; or
mapping the task identified as missing to a new agent and the new schedule is created.
12. The one or more non-transitory machine-readable information storage mediums of claim 11 , wherein the one or more task specific parameters comprising coordinates of the first location and the second location.
13. The one or more non-transitory machine-readable information storage mediums of claim 11 , wherein the first location is indicative of a pickup location and the second location is indicative of a drop location.
14. The one or more non-transitory machine-readable information storage mediums of claim 11 , wherein the one or more static agent specific parameters comprising agent speed without any payload, an agent speed with payload, an actuation time to a perform a first subtask, and an actuation time to perform a second subtask.
15. The one or more non-transitory machine-readable information storage mediums of claim 11 , wherein the one or more dynamic agent specific parameters comprising the current location and a residual energy of the agent.