Daniel, Jasfer S.; Fulgencio, Avery Nash A.
Enhancement of conflict-based search algorithm for optimization of logistics management - Undergraduate Thesis: (Bachelor of Science in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2025
ABSTRACT: The Conflict-Based Search (CBS) algorithm faces a significant problem in large multi-agent pathfinding. Its time complexity grows exponentially, hindering its use in large grids; its traditional implementation often generates suboptimal paths that increase operational costs in logistics and autonomous vehicles; and it repeatedly solves identical low-level search problems without reusing past solutions, wasting computing power and resources. To address these limitations, solutions such as Conflict Avoidance Table integrated into the A* low-level search and augmented with a tie-breaking mechanism to steer agents away from high-conflict areas while flavoring lower-cost, conflict-aware routes; a high-level branch-prioritization strategy that orders agents by Manhattan distance to their goals reducing node expansions and curbing exponential search growth; and a hierarchical caching system that stores full path solutions and partial subpath segments, enabling immediate retrieval of solved subproblems rather than recomputing them were implemented. These enhancements collectively improve routine efficiency, path optimality, and resource utilization: the tie-breaking mechanism selects the agent with lower cumulative cost and fewer conflicts, the prioritization strategy dramatically decreases search nodes, and the modular cache fetches stored results for recurring queries. Experiments across diverse grid configurations---varying grid sizes, agent counts, and obstacle densities----demonstrate that the enhanced CBS reduces average runtimes by over 90% and cuts conflicts by nearly 99%, confirming significant gains in scalability, efficiency, and resource usage. Moreover, modular architecture enables seamless integration with existing CBS frameworks, facilitating straightforward deployment. Future work will extend the caching mechanism to support dynamic replanning in real time, further enhancing adaptability in rapidly changing environments.
QA76.9 A43 D36 2025
Enhancement of conflict-based search algorithm for optimization of logistics management - Undergraduate Thesis: (Bachelor of Science in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2025
ABSTRACT: The Conflict-Based Search (CBS) algorithm faces a significant problem in large multi-agent pathfinding. Its time complexity grows exponentially, hindering its use in large grids; its traditional implementation often generates suboptimal paths that increase operational costs in logistics and autonomous vehicles; and it repeatedly solves identical low-level search problems without reusing past solutions, wasting computing power and resources. To address these limitations, solutions such as Conflict Avoidance Table integrated into the A* low-level search and augmented with a tie-breaking mechanism to steer agents away from high-conflict areas while flavoring lower-cost, conflict-aware routes; a high-level branch-prioritization strategy that orders agents by Manhattan distance to their goals reducing node expansions and curbing exponential search growth; and a hierarchical caching system that stores full path solutions and partial subpath segments, enabling immediate retrieval of solved subproblems rather than recomputing them were implemented. These enhancements collectively improve routine efficiency, path optimality, and resource utilization: the tie-breaking mechanism selects the agent with lower cumulative cost and fewer conflicts, the prioritization strategy dramatically decreases search nodes, and the modular cache fetches stored results for recurring queries. Experiments across diverse grid configurations---varying grid sizes, agent counts, and obstacle densities----demonstrate that the enhanced CBS reduces average runtimes by over 90% and cuts conflicts by nearly 99%, confirming significant gains in scalability, efficiency, and resource usage. Moreover, modular architecture enables seamless integration with existing CBS frameworks, facilitating straightforward deployment. Future work will extend the caching mechanism to support dynamic replanning in real time, further enhancing adaptability in rapidly changing environments.
QA76.9 A43 D36 2025