580 California St., Suite 400
San Francisco, CA, 94104
Key research themes
1. How can metaheuristic frameworks improve path search efficiency while maintaining adaptability across various problem domains?
This research theme investigates the design and application of metaheuristic algorithms, particularly Iterated Local Search (ILS), Greedy Randomized Adaptive Search Procedure (GRASP) with path-relinking, and Scatter Search with path relinking. These approaches focus on balancing exploration and exploitation in complex path-finding problems, often modeled as combinatorial optimization tasks. Their importance stems from their ability to effectively navigate large, multimodal, or NP-hard solution spaces with limited problem-specific knowledge, providing versatile and adaptable solution strategies.
Key finding: Iterated Local Search (ILS) constructs a sequence of solutions by iteratively perturbing and refining solutions generated by an embedded heuristic (often local search), leading to improved solution quality over random... Read more
Key finding: GRASP enhanced with path-relinking integrates intensification strategies via exploring trajectories that connect elite solutions found by multiple GRASP iterations, producing improvements in solution quality and convergence... Read more
Key finding: Scatter Search and its generalization path relinking employ strategic combination and recombination of diverse high-quality solutions to guide search. The approach balances diversification (exploring novel solution regions)... Read more
2. How do heuristic functions and multi-heuristic frameworks address complexity and efficiency challenges in path search, especially with impractical or uncalibrated heuristics?
This theme explores approaches to enhance path search by integrating heuristic guidance, including evaluation of heuristic effectiveness and frameworks that accommodate multiple heuristics, possibly inadmissible or uncalibrated. The research focuses on improving search efficiency and solution quality in shortest path and multi-objective path problems where heuristics may not perfectly estimate costs or may adversely affect traditional best-first strategies. It also considers algorithmic adaptations to manage path feasibility and complexity in large-scale or multi-criteria contexts.
Key finding: Experimental evaluation reveals that whereas heuristic functions reduce space requirements in bicriterion shortest path algorithms, they do not necessarily produce time efficiency gains; in some cases, heuristics worsen... Read more
Key finding: The paper proposes Improved Multi-Heuristic A* (MHA*), which resolves the calibration problem where inadmissible heuristics lack consistent cost correlation with the cost-to-come, by decoupling heuristic evaluations and... Read more
Key finding: ILS's modular framework allows effective tuning of perturbation strength to complement heuristic local search, acknowledging that strong interaction between heuristic characteristics and iteration mechanisms critically... Read more
3. What algorithmic strategies enable efficient and reliable path search in dynamic, stochastic, or constrained environments where path feasibility, moving obstacles, or partial information are central challenges?
This theme investigates path planning and search under uncertainty, dynamic obstacles, or multi-agent conditions. It includes mathematical modeling of search with stochastic mobility, dynamic path planning among moving obstacles via spatio-temporal indexing, and design of algorithms capable of handling failures, limited lifetimes, and route uncertainty. The focus is on deriving optimal or near-optimal search and routing strategies that minimize detection or traversal time under practical constraints.
Key finding: The study models a search process where searchers with finite random lifetimes operate in an infinite stochastic space to locate an unknown object at distance D. By representing searchers as coupled Brownian motions, the... Read more
Key finding: Through Markovian modeling of a target moving between unobservable hiding and operating areas along multiple probabilistic routes, the paper analytically determines mean detection times when sensors are placed strategically... Read more
Key finding: This approach incorporates time as a third dimension to transform moving obstacle problems in 2D into static path planning in 3D space-time, enabling collision-free path determination that respects velocity and acceleration... Read more
Key finding: The cost in total energy expended across repeated searcher deployments is evaluated alongside the average search time, quantifying efficiency trade-offs in resource-limited stochastic search under failure and destruction... Read more