000			02585nam a22001817a 4500
003			FT8920
005			20260107133601.0
050			_aQA76.9 A43 D36 2025
100	1		_aDaniel, Jasfer S.; Fulgencio, Avery Nash A.
245			_aEnhancement of conflict-based search algorithm for optimization of logistics management
264		1	_cc2025
300			_bUndergraduate Thesis: (Bachelor of Science in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2025
336			_2text _atext _btext
337			_2 unmediated _a unmediated _b unmediated
338			_2volume _avolume _bvolume
505			_aABSTRACT: 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.
942			_2lcc _cMS
999			_c37404 _d37404