Abstract

With the increasing demand for fast and efficient service in modern restaurants, robots have emerged as a promising solution to enhance customer experience. This project, Planning for Coffee Delivery Robots, focuses on designing optimal routes for delivery robots to serve coffee efficiently. The main challenge lies in minimizing energy consumption, delivery time, and operational costs while ensuring timely service and avoiding obstacles in a dynamic environment.
The methodology involves task allocation and optimization to determine the ideal number of robots, their routes, and task assignments. By integrating techniques like Simulated Annealing (SA), Genetic Algorithms (GA), Ant Colony Optimization (ACO), and Teaching-Learning-Based Optimization (TLBO), the project explores how these algorithms can be applied to optimize delivery operations. Each technique is tested through case studies within a simulated restaurant environment, modeled as a 20x20 grid with predefined table and kitchen positions.
Comparisons between these techniques are provided to evaluate their efficiency in minimizing travel distance, delivery time, and power consumption under various constraints.

Introduction

Nowadays, restaurants are searching for quicker and more effective ways to serve customers. One suggested solution is to deliver coffee to tables using robots. The goal of this project is to design these robots optimal routes so they can move fast, avoid obstacles, and use less energy which means lower cost. Making sure the robots deliver orders on time, without running out of battery or taking too long, is the difficult part. We can reduce energy consumption and speed up the service by optimizing the robots movements.

Our project, "Planning for Coffee Delivery Robots," evaluates how several robots can cooperate to provide the most effective coffee service. Reducing the distance that robots must travel, speeding up coffee delivery, and using the least amount of power are the goals. In addition, we must ensure that the robots travel at a safe speed and within the battery's limitations. This will demonstrate how robots can enhance customer service in crowded settings like restaurants.

Literature Review

The paper by Lamini, Benhlima, and Elbekri (2018), tackles the problem of path planning for autonomous mobile robots in static environments, using genetic algorithms (GA) to find optimal paths that balance distance and safety while avoiding obstacles. The main challenges addressed include generating feasible paths without premature convergence and ensuring thorough exploration of the search space through enhanced genetic operators. The authors propose improvements, including an advanced crossover operator that combines high- and low-fitness parents to enhance solution quality while maintaining diversity, a new fitness function that prioritizes straighter, safer paths, and an initial population generation method based on directed acyclic graphs (DAG). The results show that the proposed GA method outperforms existing approaches by producing smoother and more efficient paths with fewer turns and iterations, and it consistently performs well across various environments. The environment is modeled using an occupancy grid matrix where cells represent free or occupied spaces, helping the robot avoid obstacles and navigate safely.

The paper by Fetanat, Haghzad, and Shouraki (2015) addresses the problem of optimizing mobile robot path planning in dynamic environments, where obstacles can change locations, presenting challenges in finding a feasible, optimal path from the start to the target point while avoiding obstacles. A key issue highlighted is the risk of algorithms getting trapped in local minima, preventing them from achieving the global minimum, thus limiting path planning effectiveness. To solve this, the authors employ three evolutionary algorithms—Genetic Algorithm (GA), Pattern Search (PS), and Particle Swarm Optimization (PSO)—to optimize path planning. Each method is evaluated in a grid-based environment with both static and dynamic obstacles. The results show that PSO is the most effective at minimizing the objective function, providing smoother and safer paths, while PS is the fastest in terms of execution time. In contrast, GA performed worst in both optimization and time efficiency. The use of a grid-based environment allowed the algorithms to navigate obstacles effectively, with PSO consistently demonstrating superior performance in dynamic environments.

Palac (2023) explores the optimization of a mobile delivery robot's navigation within a multi-story building using Dijkstra’s algorithm. A static navigation tree was developed, representing weighted paths between manually defined origin and delivery points, where each node corresponds to a feasible location within the building. The researchers applied this path planning method to create a weighted navigation system for the robot's movement. Simulation results demonstrated the efficiency of the proposed method in facilitating effective routing for the robot. While quantitative details were not provided, the analysis confirmed that the algorithm allowed the robot to navigate complex multi-story environments efficiently. The study highlights the potential of Dijkstra’s algorithm for optimizing navigation in dynamic indoor settings, particularly for delivery robots in multi-level buildings.

Ravankar (2021) aims to make path planner of autonomous robots to ensure efficient charging of robots while doing its work, taking in the consideration battery power, task priority and the location of the robot on the map aiming to make efficient way for robots charging. In the system they made they were conducting which robot will go to the station in different scenarios as they made 4 experiments with different environment. first robot needs to recharge and an empty charging point is available. Second Investigated a situation where all charging points are occupied and a robot need to charge. Third was made in bigger and more complex environment with obstacles and many chargers. Last Examined the robot's ability to access the nearest empty charging point when multiple points are available. Then start making path using A* technique and update in the real time database to avoid collision with others if they will path in near coordinates. The results show more efficient path planning comparing to traditional path planning that rely on sequence search, which make optimizing path planning as it takes into consideration many criteria not only neediness of charge such as traditional solutions.

The paper by Zafar and Mohanta (2018), addresses critical challenges in path planning algorithms and optimization for mobile robots operating in both static and dynamic environments. The authors advocate for the development of meta-heuristic methods, which offer promising solutions. The paper outlines several optimization techniques applicable to mobile robot path planning, including Ant Colony Optimization, Particle Swarm Optimization (PSO), Bacterial Foraging Optimization, Firefly Algorithm, Genetic Algorithms, and hybrid approaches. Key findings reveal that while classical methods may be easier to implement, they often require precise navigational parameters, whereas meta-heuristic techniques like PSO and Bacterial Foraging Optimization demonstrate significant improvements in dynamic settings, characterized by quicker convergence times and smoother trajectories. The authors also highlight the use of grid-based methods, which rely on matrices to organize environmental information, facilitating path planning by classifying areas as free or occupied. Overall, the insights from this review stress the importance of selecting appropriate algorithms based on the specific requirements of mobile robotics applications, particularly in navigation and task planning scenarios.

Methodology

In this methodology section, the core concept behind task allocation optimization will be explored in depth. Task allocation is a critical aspect in robotics and multi-agent systems, particularly in environments where multiple robots are deployed to execute tasks efficiently while balancing workload and minimizing operational costs. In the context of coffee delivery, the primary goal of this optimization is to determine the optimal number of robots needed and assign specific robots to deliver coffee to designated tables. This ensures that tasks are completed in the most efficient manner, minimizing costs associated with factors such as travel distance, delivery time, or energy consumption.

The formulation for our project is as follows:

• T represents the total waiting time for the customers.
• D represents the total distance covered by the robots.
• P represents the maximum power used by any robot.
• The weights assigned to each variable are:
• α is the weight for waiting time.
• β is the weight for distance.
• γ is the weight for the maximum power used.

The objective function is described by the following equation:

The above figure shows the restaurant layout with the starting points for the robots journey, as well as the tables with it’s positions.

The decision variables in our problem are:

• Number of Robots
• Number of Orders and it’s locations
• Order distribution among the robots

The Objective Functions in our problem are:

• Minimize total distance traveled by the robots
• Minimize the total time of delivery
• Minimize the cost (maximum power usage)

The Constrains in our problem are:

• Capacity of the Robot’s battery (covers 50 meters max)
• Robots must avoid obstacles and other robots in the environment
• Maximum number of robots is 6

Assumptions:

• We assume the Robot’s constant speed of 2 m/s.
• Area of the restaurant is fixed (20 x 20).
• There are two starting points where the robots take the
orders that should be delivered (5,0) and (15,0).
• We assume that each Robot could as much orders as needed at once (no capacity constrain).
• We assume we have 6 fixed tables, at locations (4,9); (7,12); (10,19); (11,11); (13,3); (18,16).
• Task allocation is calculated and decided from the starting point.

We will now walk through our code to highlight the key sections and functions. Additionally, we’ll provide a quick overview of the assumptions and constraints we applied when setting up the problem.

Initializing Steps:

• The restaurant is modeled as a 20x20 grid (20m x 20m).
• There are two kitchens, or starting points for the robots, located at coordinates (5,0) and (15,0).
• Tables are positioned at predefined locations, and a list of orders is assigned to each robot randomly.

Distance Calculation:

The function "calculate_distance" computes the Euclidean distance between two points. This helps determine the distance from the starting point to the tables, as well as from one table to the next.

Robot Assignment and Order Allocation:

• Robots are assigned to one of the kitchens, and their movement from the kitchen to each table is simulated based on assigned orders.
• The function "calculate_robot_total_distance" calculates the total distance traveled by each robot. It ensures that no robot exceeds the 50-meter battery limit. If exceeded, the solution is considered infeasible since not all orders would be fully delivered.

Order Duration and Time Calculation:

• The function "calculate_duration" computes the time required for a robot to cover a specific distance based on a fixed speed of 2 m/s.

Energy Consumption:

• The function "calculate_power" determines power usage based on the distance traveled by each robot while ensuring that energy consumption remains within the feasible 50-meter limit. It returns the maximum power consumed by a robot.

Objective Function:

• The function "objective_function" integrates three main factors—time, distance, and power consumption—using the weights α, β, and γ to compute a fitness value. The optimization process aims to minimize this fitness value by reducing total distance, time, and power usage (cost).

Feasibility Check:

• If any robot's total distance exceeds the battery capacity, the solution is considered infeasible; otherwise, the fitness value is returned.

Simulated Annealing (SA)

Several scenarios were tested to examine the algorithm’s effectiveness under different conditions, such as changing the number of robots, and where they are assigned. The outcomes focus on key performance indicators like total distance traveled, power consumption, and task completion time, all while ensuring the robots stay within their battery limits. The two decision variables that Simulated Annealing randomizes are the number of robots and the assignment of robots to orders. Below is an explanation of the code:

Robot Initialization:

• The number of robots is initially got random of number between 1 and 6.
• Then, each robot got randomly assigns to either kitchen 1 or kitchen 2, which means either he will start from (5,0) or (15,0)

Simulated Annealing (SA) Process:

• It starts with an initial solution (as mentioned in the above section), and it evaluates the fitness of this solution, and then attempts to improve it by making random changes. These changes is that we chose a new robot randomly, and swap it with one of the orders in a random way.
• The acceptance of worse solutions is controlled by the "cooling schedule" (starting temperature of 1000, and a cooling rate of 10).
• If the new solution's fitness is better, it is accepted. Otherwise, a probability is calculated using the acceptance probability formula math.exp((old_fitness - new_fitness) / time) to potentially accept worse solutions. Sometimes accepting worse solutions is needed in order to do more exploration.
• The temperature is reduced during each iteration, leading to fewer random changes as the algorithm converges.

Output:

• The final section prints the results if the solution is feasible, including total distance, time, and power usage for each robot. It also checks if the solution is feasible or not. Also, It prints all of the iterations in the SA Algorithm.

SA Case Studies

Case Study 1

Initial Conditions:

• There were 6 orders and 4 robots
• Arranged to the 6 orders as follows [(0, 2), (1, 5), (2, 3), (3, 2), (4, 4), (5, 5)]
• It started with initial fitness value of 960.26

Output:

• It ended up using 3 different robots
• With the following arrangement [(0, 4), (1, 4), (2, 4), (3, 4), (4, 3), (5, 5)]
• It ended with fitness value of 618.89

Case Study 2

Initial Conditions:

• There were 6 orders with 4 robots
• Arranged to the 6 orders as follows [(0, 2), (1, 5), (2, 2), (3, 0), (4, 4), (5, 5)]
• It started with initial fitness value of 758.70

Output:

• It ended up using 4 different robots
• With the following arrangement [(0, 5), (1, 1), (2, 1), (3, 0), (4, 3), (5, 0)]
• It ended with fitness value of 730.71

Case Study 3

Initial Conditions:

• There were 6 Orders and 5 robots
• Arranged to the 4 orders as follows [(0, 0), (1, 1), (2, 2), (3, 5), (4,3), (5,1)]
• It started with initial fitness value of 1026.76

Output:

• It ended up using 3 different robots
• With the following arrangement [(0, 2), (1, 2), (2, 2), (3, 4), (4, 1), (5, 4)]
• It ended with fitness value of 567.80

Case Study 4

Initial Conditions:

• There were 4 Orders and 3 robots
• Arranged to the 4 orders as follows [(0, 1), (1, 2), (2, 3), (3,2)]
• It started with initial fitness value of 663.79

Output:

• It ended up using 2 robots
• With the following arrangement [(0, 1), (1, 1), (2, 1), (3, 0)]
• It ended with fitness value of 478.49

The acceptance of worse solutions at higher temperatures helps the algorithm avoid getting stuck in local minima, but this changes as the temperature decreases. The fitness function, which considers time, distance, and power consumption, ensures that all critical factors are optimized based on their assigned weights.

Genetic Algorithms (GA)

In this section, we present the results of applying the Genetic Algorithm (GA) to the problem of optimizing robot assignments in a restaurant environment. Several scenarios were tested to examine the algorithm’s effectiveness under various conditions, such as changing the number of robots and their specific task assignments. The outcomes focus on key performance indicators like total distance traveled, power consumption, and task completion time, while ensuring that all robots operate within their battery constraints.

Initial Conditions

Here we will talk about the initial conditions of the algorithm and its structure and at the end why we used this structure for the GA algorithm

• 5 chromosomes in 1 population
• 20% of the population is elite, so 1 chromosome
• 60% of the population is crossover, so 3 chromosomes
• Crossover is between elite and 2nd best, 2nd best and third best also we uses one-point cross over technique
• 20% of the population is mutation, so 1 chromosome
• Mutation change 2 task allocation with random 2 robots.
• Finish after 100 iterations or after 100 populations is formed

We choose this criteria based on trials and distinguished the best combination. The elite is the best solution we found till now and the crossover is trying to found the minimal solution or best solution beside the elite. Mutation is responsible for discovering the world and find better solutions and we did not make crossover with it to not be stuck in area which does not even has good solution.

GA case studies

Case Study 1: 6 orders

• Initial Population:
  [[(0, 0), (1, 1), (2, 1), (3, 1), (4, 0), (5, 2)],
  [(0, 4), (1, 3), (2, 1), (3, 1), (4, 2), (5, 5)],
  [(0, 4), (1, 3), (2, 5), (3, 1), (4, 3), (5, 1)],
  [(0, 2), (1, 0), (2, 0), (3, 1), (4, 1), (5, 5)],
  [(0, 1), (1, 0), (2, 0), (3, 5), (4, 4), (5, 3)]]

• Last Population:
  [[(0, 1), (1, 1), (2, 1), (3, 4), (4, 5), (5, 4)],
  [(0, 1), (1, 1), (2, 1), (3, 4), (4, 5), (5, 4)],
  [(0, 1), (1, 1), (2, 1), (3, 4), (4, 5), (5, 4)],
  [(0, 4), (1, 1), (2, 1), (3, 4), (4, 5), (5, 4)],
  [(0, 2), (1, 5), (2, 2), (3, 0), (4, 5), (5, 1)]]

• Here the algorithm found the best solution which is 567 in the 36 iteration so then it completed the 100 iteration without any changes

Case Study 2: 6 orders

• Initial Population:
  [[(0, 2), (1, 0), (2, 5), (3, 4), (4, 2), (5, 0)],
  [(0, 1), (1, 2), (2, 0), (3, 2), (4, 5), (5, 3)],
  [(0, 1), (1, 3), (2, 1), (3, 5), (4, 0), (5, 5)],
  [(0, 3), (1, 1), (2, 1), (3, 1), (4, 2), (5, 0)],
  [(0, 1), (1, 5), (2, 3), (3, 5), (4, 1), (5, 4)]]

• Last Population:
  [[(0, 0), (1, 0), (2, 3), (3, 0), (4, 5), (5, 0)],
  [(0, 0), (1, 0), (2, 3), (3, 0), (4, 5), (5, 0)],
  [(0, 2), (1, 0), (2, 3), (3, 0), (4, 5), (5, 0)],
  [(0, 0), (1, 0), (2, 3), (3, 0), (4, 5), (5, 0)],
  [(0, 0), (1, 1), (2, 1), (3, 0), (4, 4), (5, 1)]]

• Here the algorithm found good solution which was 625 but at the end didn't reach to the best solution.

Case Study 3 : 4 orders

• Initial Population:
  [[(0, 2), (1, 4), (2, 0), (3, 5)],
  [(0, 5), (1, 5), (2, 2), (3, 0)],
  [(0, 4), (1, 3), (2, 4), (3, 2)],
  [(0, 1), (1, 3), (2, 3), (3, 0)],
  [(0, 1), (1, 2), (2, 5), (3, 5)]]

• Last Population:
  [[(0, 1), (1, 1), (2, 1), (3, 3)],
  [(0, 1), (1, 1), (2, 1), (3, 3)],
  [(0, 1), (1,5), (2, 1), (3, 3)],
  [(0, 1), (1, 1), (2, 1), (3, 2)],
  [(0, 1), (1, 0), (2, 3), (3, 2)]]

Here we changed the orders to be only on 4 tables and the algorithm found good solution but not the best. As we can see in this graph the fitness values decreased because their is less orders

Ant Colony Optimization (ACO)

In this section, we discuss the application of the Ant Colony Optimization (ACO) algorithm to the problem of robot assignments in a restaurant environment. Using the ACO algorithm, each "ant" simulated the process of assigning robots to tasks by exploring various paths based on pheromone trails and heuristic factors. These pheromone trails, influenced by the success of previous paths, allowed the ants to iteratively converge toward optimized solutions.

Initial Conditions

• Pheromone evaporation rate, which controls the decay of pheromone intensity is 0.1.
• Constant controlling the pheromone deposition by ants is (q=10).
• Three ants are used to simulate the optimization process, each constructing a path based on pheromone levels and heuristic rules.
• The initial pheromone levels are set to 1 for all paths, with the last column in the pheromone matrix set to 6 to represent the total sum of pheromone values.

ACO Case Studies

Case Study 1:

• Initial Pheromone: [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6]
• Final Pheromone: [[0.0, 0.01, 0.1, 0.0, 0.04, 0.16, 0.32], [0.03, 0.0, 0.03, 0.05, 0.07, 0.14, 0.32], [0.02, 0.2, 0.02, 0.04, 0.04, 0.0, 0.32], [0.24, 0.0, 0.02, 0.03, 0.03, 0.0, 0.32], [0.0, 0.03, 0.08, 0.01, 0.04, 0.16, 0.32], [0.08, 0.11, 0.0, 0.0, 0.12, 0.01, 0.32]]
• Best combination: [(0, 3), (1, 3), (2, 3), (3, 1), (4, 5), (5, 1)]
• Best fitness: 643.5797144523227

Case Study 2:

• Initial Pheromone: [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6]
• Final Pheromone: [[0.02, 0.03, 0.22, 0.04, 0.05, 0.0, 0.36], [0.02, 0.0, 0.27, 0.01, 0.01, 0.04, 0.36], [0.02, 0.16, 0.1, 0.01, 0.06, 0.0, 0.36], [0.16, 0.04, 0.05, 0.02, 0.0, 0.08, 0.36], [0.15, 0.03, 0.01, 0.11, 0.01, 0.05, 0.36], [0.01, 0.07, 0.15, 0.1, 0.02, 0.0, 0.36]]
• Best combination: [(0, 1), (1, 1), (2, 1), (3, 2), (4, 3), (5, 2)]
• Best fitness: 578.2541010904059

Case Study 3:

• Initial Pheromone: [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6]
• Final Pheromone: [[0.07, 0.07, 0.06, 0.01, 0.0, 0.16, 0.36], [0.02, 0.14, 0.11, 0.0, 0.03, 0.05, 0.36], [0.03, 0.0, 0.21, 0.0, 0.0, 0.12, 0.36], [0.02, 0.12, 0.07, 0.05, 0.0, 0.1, 0.36], [0.01, 0.11, 0.0, 0.04, 0.19, 0.01, 0.36], [0.0, 0.04, 0.08, 0.05, 0.17, 0.01, 0.36]]
• Best combination: [(0, 2), (1, 2), (2, 2), (3, 5), (4, 4), (5, 2)]
• Best fitness: 567.062015593209

Case Study 4:

• Initial Pheromone: [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 6]

• Final Pheromone: [[0.09, 0.0, 0.13, 0.01, 0.12, 0.0, 0.34], [0.09, 0.0, 0.12, 0.0, 0.07, 0.07, 0.34], [0.09, 0.07, 0.06, 0.01, 0.01, 0.12, 0.34], [0.06, 0.21, 0.01, 0.0, 0.03, 0.03, 0.34], [0.0, 0.15, 0.01, 0.13, 0.02, 0.03, 0.34], [0.19, 0.01, 0.0, 0.09, 0.02, 0.04, 0.34]]

• Best combination: [(0, 0), (1, 0), (2, 1), (3, 0), (4, 3), (5, 1)]

• Best fitness: 623.4225428965622

Teaching-Learning-Based Optimization (TLBO)

In this section, we discuss the application of the Teaching-Learning-Based Optimization (TLBO) algorithm to the problem of robot assignments in a restaurant environment. Using the TLBO algorithm, each solution in the population simulated the process of assigning robots to tasks through two key phases: the teacher phase and the learner phase. In the teacher phase, the best solution influenced other solutions to improve their performance, while in the learner phase, solutions improved further by interacting and learning from one another. This iterative process enabled the solutions to converge toward optimized assignments efficiently.

Initial Conditions

• Population Size: The algorithm simulated a population of 10 students (solutions), each representing a feasible assignment of tasks to robots.
• Feasibility Constraints: Solutions violating feasibility constraints were discarded or modified during the search process.
• Diversity Injection: To avoid premature convergence, 20% of the population was replaced with new feasible solutions every 20 iterations.

TLBO Case Studies

Case Study 1:}

• Best combination: [(0, 2), (1, 2), (2, 3), (3, 2), (4, 4), (5, 3)]
• Best fitness: 623.4225428965622

Case Study 2:

• Best combination:[(0, 2), (1, 2), (2, 2), (3, 3), (4, 4), (5, 3)]
• Best fitness: 567.8007548683935

GA VS SA VS ACO VS TLBO Comparison

Comparison between Genetic Algorithm (GA) and Simulated Annealing (SA) and Ant Colony (ACO) and TLBO over 20 runs}

Conclusion

This study successfully explored various optimization techniques to enhance the efficiency of coffee delivery robots in a restaurant setting. By employing Simulated Annealing (SA), Genetic Algorithms (GA), Ant Colony Optimization (ACO), and Teaching-Learning-Based Optimization (TLBO), we achieved significant improvements in minimizing travel distance, energy consumption, and delivery time. Among the tested techniques, all achieved the best fitness score of 567 in their respective scenarios. However, the approaches varied in efficiency, with ACO showing the lowest standard deviation, indicating better consistency, and SA being the fastest in terms of computation time. Overall, the results validate the efficacy of optimization algorithms in real-time task allocation and route planning for multi-robot systems. This research underscores the potential of integrating advanced optimization techniques to revolutionize robotic automation in dynamic environments like restaurants.

Future Work

Future research will focus on transitioning from simulated environments to real-world implementations, incorporating dynamic task allocation with real-time adaptability using advanced machine learning models. Additionally, exploring hybrid optimization techniques and integrating multi-objective criteria will provide a more holistic approach to balancing energy efficiency, service speed, and operational costs. To further enhance adaptability, the inclusion of real-time feedback mechanisms and obstacle prediction systems can be integrated, ensuring optimal performance in unpredictable environments. Expanding the system's scalability to accommodate larger spaces and more complex layouts will also be prioritized, paving the way for broader applications of cooperative robotic systems in service industries.