Distributed task allocation in Drone Programming - Step-by-Step Execution

Concept Flow - Distributed task allocation

Start: Tasks and Drones Initialized

↓

Broadcast Tasks to Drones

↓

Each Drone Evaluates Tasks

↓

Drones Bid or Score Tasks

↓

Conflict Resolution Among Drones

↓

Assign Tasks to Drones

↓

Drones Execute Assigned Tasks

↓

Report Completion

↓

End

The system starts with tasks and drones, broadcasts tasks, drones evaluate and bid, conflicts are resolved, tasks assigned, executed, and completion reported.

Execution Sample

Drone Programming

tasks = ['Scan Area', 'Deliver Package', 'Take Photos']
drones = ['Drone1', 'Drone2']
assignments = {}
for task in tasks:
    best_drone = min(drones, key=lambda d: len(assignments.get(d, [])))
    assignments.setdefault(best_drone, []).append(task)
print(assignments)

This code assigns tasks to drones by giving each new task to the drone with the fewest current tasks.

Execution Table

Step	Task	Drone Loads	Selected Drone	Assignments After Step
1	Scan Area	{'Drone1': 0, 'Drone2': 0}	Drone1	{'Drone1': ['Scan Area']}
2	Deliver Package	{'Drone1': 1, 'Drone2': 0}	Drone2	{'Drone1': ['Scan Area'], 'Drone2': ['Deliver Package']}
3	Take Photos	{'Drone1': 1, 'Drone2': 1}	Drone1	{'Drone1': ['Scan Area', 'Take Photos'], 'Drone2': ['Deliver Package']}

💡 All tasks assigned; loop ends after last task.

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
assignments	{}	{'Drone1': ['Scan Area']}	{'Drone1': ['Scan Area'], 'Drone2': ['Deliver Package']}	{'Drone1': ['Scan Area', 'Take Photos'], 'Drone2': ['Deliver Package']}	{'Drone1': ['Scan Area', 'Take Photos'], 'Drone2': ['Deliver Package']}

Key Moments - 2 Insights

Why does the code choose the drone with the fewest tasks for each new task?

Choosing the drone with the fewest tasks balances the workload, preventing one drone from getting overloaded. This is shown in the execution_table where the 'Selected Drone' is always the one with the smallest current 'Drone Loads'.

What happens if two drones have the same number of tasks?

The min function picks the first drone it finds with the smallest load. For example, at step 3 both drones have 1 task, so 'Drone1' is chosen because it appears first in the list.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2. Which drone is assigned the 'Deliver Package' task?

A Drone1

B Both drones

C Drone2

D No drone assigned

💡 Hint

Check the 'Selected Drone' column at Step 2 in the execution_table.

At which step does 'Drone1' get assigned its second task?

A Step 3

B Step 2

C Step 1

D Never

💡 Hint

Look at the 'Assignments After Step' column for 'Drone1' in the execution_table.

If a third drone 'Drone3' was added with no tasks, which drone would get the 'Take Photos' task at Step 3?

A Drone1

B Drone3

C Drone2

D No assignment

💡 Hint

Refer to the variable_tracker and execution_table logic: the drone with fewest tasks gets the next task.

Concept Snapshot

Distributed task allocation assigns tasks to multiple drones fairly.
Each drone evaluates tasks and bids or scores them.
Tasks are assigned to balance workload and avoid conflicts.
Drones execute tasks and report completion.
Simple method: assign each new task to drone with fewest current tasks.

Full Transcript

Distributed task allocation starts by initializing tasks and drones. Tasks are broadcast to drones, which evaluate and bid on them. Conflicts are resolved to avoid duplicate assignments. Tasks are assigned to drones, which then execute them and report completion. The example code assigns tasks to drones by always choosing the drone with the fewest assigned tasks so far. The execution table shows step-by-step which drone gets each task and how assignments grow. Key points include balancing workload and handling ties by choosing the first drone found. The quizzes check understanding of task assignment steps and how adding drones affects allocation.

Practice

1. What is the main goal of distributed task allocation in drone programming?

easy

A. To share work fairly among drones without a central controller

B. To make one drone do all the tasks quickly

C. To randomly assign tasks without any order

D. To stop drones from communicating with each other

Solution

1. Step 1: Understand distributed task allocation

   It means dividing tasks so all drones get work fairly.

2. Step 2: Identify the goal in drone programming

   The goal is to avoid a single controller and let drones share tasks efficiently.

3. Final Answer:

   To share work fairly among drones without a central controller -> Option A

4. Quick Check:

   Distributed task allocation = fair work sharing [OK]

Hint: Remember: share tasks fairly, no single boss drone [OK]

Common Mistakes:

• Thinking one drone does all tasks
• Assuming tasks are assigned randomly
• Believing drones don't communicate

2. Which of the following is the correct way to assign tasks to drones in a round-robin style using Python?

easy

A. task_index * len(drones)

B. len(drones) % task_index

C. task_index + len(drones)

D. task_index % len(drones)

Solution

1. Step 1: Understand round-robin assignment

   Round-robin cycles through drones by using modulo with drone count.

2. Step 2: Apply modulo operator correctly

   Using task_index % len(drones) cycles task indices over drone list indices.

3. Final Answer:

   task_index % len(drones) -> Option D

4. Quick Check:

   Modulo with drone count cycles tasks [OK]

Hint: Use modulo (%) with drone count to cycle tasks [OK]

Common Mistakes:

• Reversing modulo operands
• Adding or multiplying instead of modulo
• Using modulo with wrong variable

3. What will be the output of this code snippet?

tasks = ['scan', 'deliver', 'map', 'charge']
drones = ['droneA', 'droneB']
assignments = {}
for i, task in enumerate(tasks):
    drone = drones[i % len(drones)]
    assignments.setdefault(drone, []).append(task)
print(assignments)

medium

A. {'droneA': ['scan', 'map'], 'droneB': ['deliver', 'charge']}

B. {'droneA': ['scan', 'deliver'], 'droneB': ['map', 'charge']}

C. {'droneA': ['scan'], 'droneB': ['deliver', 'map', 'charge']}

D. {'droneA': ['charge'], 'droneB': ['scan', 'deliver', 'map']}

Solution

1. Step 1: Assign tasks using modulo

   Tasks are assigned to drones cycling through drones list by i % 2.

2. Step 2: Map tasks to drones

   Index 0: 'scan' -> droneA, 1: 'deliver' -> droneB, 2: 'map' -> droneA, 3: 'charge' -> droneB.

3. Final Answer:

   {'droneA': ['scan', 'map'], 'droneB': ['deliver', 'charge']} -> Option A

4. Quick Check:

   Modulo cycles tasks evenly [OK]

Hint: Match task index modulo drone count to assign tasks [OK]

Common Mistakes:

• Mixing task order in assignments
• Ignoring modulo cycling
• Appending tasks to wrong drone

4. Identify the error in this drone task allocation code:

drones = ['D1', 'D2', 'D3']
tasks = ['photo', 'survey', 'deliver']
assignments = {}
for i in range(len(tasks)):
    drone = drones[i // len(drones)]
    assignments.setdefault(drone, []).append(tasks[i])
print(assignments)

medium

A. assignments.setdefault is used incorrectly

B. Using range(len(tasks)) is incorrect for looping

C. Using integer division (//) instead of modulo (%) assigns all tasks to the first drone

D. The drones list should be empty

Solution

1. Step 1: Check drone index calculation

   Using i // len(drones) results in index 0 for i=0,1,2 (len(drones)=3), assigning all tasks to 'D1' instead of cycling round-robin.

2. Step 2: Identify correct operator

   Modulo (%) should be used to cycle through drone indices safely.

3. Final Answer:

   Using integer division (//) instead of modulo (%) assigns all tasks to the first drone -> Option C

4. Quick Check:

   Use modulo (%) to cycle indices [OK]

Hint: Use % not // to cycle through drone indices [OK]

Common Mistakes:

• Confusing // with %
• Thinking range(len(tasks)) is wrong
• Misusing setdefault method

5. You have 3 drones and 7 tasks. You want to assign tasks so each drone gets tasks in a round-robin way but skip any task named 'wait'. Which code snippet correctly implements this?

hard

A. assignments = {}
for i, task in enumerate(tasks):
if task == 'wait':
continue
drone = drones[len(drones) % i]
assignments.setdefault(drone, []).append(task)

B. assignments = {}
for i, task in enumerate(tasks):
drone = drones[i % len(drones)]
if task != 'wait':
assignments.setdefault(drone, []).append(task)

C. assignments = {}
for task in tasks:
if task == 'wait':
continue
drone = drones[tasks.index(task) % len(drones)]
assignments.setdefault(drone, []).append(task)

D. assignments = {}
for i in range(len(tasks)):
if tasks[i] == 'wait':
continue
drone = drones[i // len(drones)]
assignments.setdefault(drone, []).append(tasks[i])

Solution

1. Step 1: Filter out 'wait' tasks correctly

   Check task != 'wait' before assigning to drones.

2. Step 2: Assign tasks using modulo for round-robin

   Use i % len(drones) to cycle drones correctly.

3. Step 3: Avoid using index() inside loop to prevent errors with duplicates

   Using tasks.index(task) can cause wrong drone assignment if tasks repeat.

4. Final Answer:

   assignments = {} for i, task in enumerate(tasks): drone = drones[i % len(drones)] if task != 'wait': assignments.setdefault(drone, []).append(task) -> Option B

5. Quick Check:

   Filter first, then assign with modulo [OK]

Hint: Check task before assign; use modulo for drone cycling [OK]

Common Mistakes:

• Using integer division instead of modulo
• Using tasks.index() causing wrong assignments
• Not skipping 'wait' tasks properly