Author name cluster

Md. Mosaddek Khan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

JAAMAS Journal 2025 Journal Article

Optimizing node selection in search based multi-agent path finding

Md. Ahasanul Alam
Shekhar Mahmud
Md. Mosaddek Khan

Abstract The Multi-Agent Path Finding (MAPF) problem involves the task of finding paths for multiple agents that want to reach their destinations without obstructing other agents. Although MAPF is essential for numerous real-world applications, finding an optimal solution to this problem is NP-hard. Many approaches have been proposed in the literature, offering sub-optimal solutions to improve runtime efficiency. Lazy Constraints Addition search for MAPF (LaCAM) is a state-of-the-art sub-optimal MAPF algorithm that employs tree-based lazy successor generation to minimize planning effort. However, the success of the algorithm heavily relies on the effective selection of nodes for expansion. LaCAM employs a fixed heuristic throughout the entire search process, disregarding the agents’ preferences or characteristics of the underlying environment. Nevertheless, experiments with various heuristics indicate that no single heuristic consistently outperforms others across all scenarios. Consequently, in diverse environments, as the number of agents increases, reliance on a single, general heuristic leads to diminished runtime performance. Against this backdrop, with the intent to further speed up the runtime, we propose a novel approach, called eLaCAM, that adaptively selects nodes during the search process considering the current scenario of the environment and agents preferences. We introduce two distinct variants of eLaCAM. The first, eLaCAM-stat, statistically analyses previous results of using different heuristics and selects nodes accordingly. The second variant, eLaCAM-ML, analyze the environment by extracting necessary features to guide a machine learning framework in assisting adaptive node selection during the search process. Our extensive empirical results illustrate a notable improvement in runtime and a reduction in the search space compared to state-of-the-art MAPF algorithms.

Details DOI

EAAI Journal 2023 Journal Article

A particle swarm inspired approach for continuous distributed constraint optimization problems

Moumita Choudhury
Amit Sarker
Samin Yaser
Md. Maruf Al Alif Khan
William Yeoh
Md. Mosaddek Khan

Distributed Constraint Optimization Problems (DCOPs) are a widely studied framework for coordinating interactions in cooperative multi-agent systems. In classical DCOPs, variables owned by agents are assumed to be discrete. However, in many applications, such as target tracking or sleep scheduling in sensor networks, continuous-valued variables are more suitable than discrete ones. To better model such applications, researchers have proposed Continuous DCOPs (C-DCOPs), an extension of DCOPs, that can explicitly model problems with continuous variables. The state-of-the-art approaches for solving C-DCOPs experience either onerous memory or computation overhead and are unsuitable for non-differentiable optimization problems. To address this issue, we propose a new C-DCOP algorithm, namely Particle Swarm Optimization Based C-DCOP (PCD), which is inspired by Particle Swarm Optimization (PSO), a well-known centralized population-based approach for solving continuous optimization problems. In recent years, population-based algorithms have gained significant attention in classical DCOPs due to their ability in producing high-quality solutions. Nonetheless, to the best of our knowledge, this class of algorithms has not been utilized to solve C-DCOPs and there has been no work evaluating the potential of PSO in solving classical DCOPs or C-DCOPs. In light of this observation, we adapted PSO, a centralized algorithm, to solve C-DCOPs in a decentralized manner. The resulting PCD algorithm not only produces good-quality solutions but also finds solution without any requirement for derivative calculations. Moreover, we design a crossover operator that can be used by PCD to further improve the quality of solutions found. Finally, we theoretically prove that PCD is an anytime algorithm and empirically evaluate PCD against the state-of-the-art C-DCOP algorithms in a wide variety of benchmarks.

Details DOI

AAMAS Conference 2022 Conference Paper

A Simulation Based Online Planning Algorithm for Multi-Agent Cooperative Environments

Rafid Ameer Mahmud
Fahim Faisal
Saaduddin Mahmud
Md. Mosaddek Khan

Multi-agent Markov Decision Process (MMDP) has been an effective way of modelling sequential decision making algorithms for multi-agent cooperative environments. However, challenges such as exponential size of action space and dynamic changes limit the efficacy of proposed solutions. This paper propose a scalable and robust algorithm that can effectively solve MMDPs in real time. Simulation, pruning, and prediction are the three key components of the algorithm. The simulation component enables real time solutions by using a novel iterative pruning technique which in turn makes use of the prediction component trained with self play data. The algorithm is self-sustained as it generates new training data from simulation and gradually becomes better. Furthermore, we show empirical results demonstrating the capabilities of the algorithm and compare them with existing MMDP solvers.

PDF

AAMAS Conference 2021 Conference Paper

A Local Search Based Approach to Solve Continuous DCOPs

Amit Sarker
Moumita Choudhury
Md. Mosaddek Khan

Distributed Constraint Optimization Problems (DCOPs) are a suitable formulation for coordinating interactions (i. e. constraints) in cooperative multi-agent systems. The traditional DCOP model assumes that variables owned by the agents can take only discrete values and constraints’ cost functions are defined for every possible value assignment of a set of variables. While this formulation is often reasonable, there are many applications where the decision variables are continuous-valued and constraints are in functional form. To overcome this limitation, Continuous DCOPs (C-DCOPs), an extension of the DCOPs model has been proposed that is able to formulate problems having continuous variables. The existing methods for solving C-DCOPs come with a huge computation and communication overhead. In this paper, we apply continuous nonlinear optimization methods on Cooperative Constraint Approximation (CoCoA) algorithm, which is a non-iterative, fast incomplete local search approach for solving DCOPs. We empirically show that our algorithm is able to provide high-quality solutions at the expense of smaller communication cost and execution time compared to the state-of-the-art C-DCOP algorithms.

PDF

AAMAS Conference 2021 Conference Paper

Accelerating Recursive Partition-Based Causal Structure Learning

Md. Musfiqur Rahman
Ayman Rasheed
Md. Mosaddek Khan
Mohammad Ali Javidian
Pooyan Jamshidi
Md. Mamun-Or-Rashid

Causal structure discovery from observational data is fundamental to the causal understanding of autonomous systems such as medical decision support systems, advertising campaigns and selfdriving cars. This is essential to solve well-known causal decision making and prediction problems associated with those real-world applications. Recently, recursive causal discovery algorithms have gained particular attention among the research community due to their ability to provide good results by using Conditional Independent (CI) tests in smaller sub-problems. However, each of such algorithms needs a refinement function to remove undesired causal relations of the discovered graphs. Notably, with the increase of the problem size, the computation cost (i. e. , the number of CI-tests) of the refinement function makes an algorithm expensive to deploy in practice. This paper proposes a generic causal structure refinement strategy that can locate the undesired relations with a small number of CI-tests, thus speeding up the algorithm for large and complex problems. We theoretically prove the correctness of our algorithm. We then empirically evaluate its performance against the state-ofthe-art algorithms in terms of solution quality and completion time in synthetic and real datasets.

PDF

AAAI Conference 2020 Conference Paper

A Particle Swarm Based Algorithm for Functional Distributed Constraint Optimization Problems

Moumita Choudhury
Saaduddin Mahmud
Md. Mosaddek Khan

Distributed Constraint Optimization Problems (DCOPs) are a widely studied constraint handling framework. The objective of a DCOP algorithm is to optimize a global objective function that can be described as the aggregation of several distributed constraint cost functions. In a DCOP, each of these functions is deﬁned by a set of discrete variables. However, in many applications, such as target tracking or sleep scheduling in sensor networks, continuous valued variables are more suited than the discrete ones. Considering this, Functional DCOPs (F-DCOPs) have been proposed that can explicitly model a problem containing continuous variables. Nevertheless, state-of-the-art F-DCOPs approaches experience onerous memory or computation overhead. To address this issue, we propose a new F-DCOP algorithm, namely Particle Swarm based F-DCOP (PFD), which is inspired by a meta-heuristic, Particle Swarm Optimization (PSO). Although it has been successfully applied to many continuous optimization problems, the potential of PSO has not been utilized in F-DCOPs. To be exact, PFD devises a distributed method of solution construction while signiﬁcantly reducing the computation and memory requirements. Moreover, we theoretically prove that PFD is an anytime algorithm. Finally, our empirical results indicate that PFD outperforms the state-of-the-art approaches in terms of solution quality and computation overhead.

PDF Details

IJCAI Conference 2020 Conference Paper

Learning Optimal Temperature Region for Solving Mixed Integer Functional DCOPs

Saaduddin Mahmud
Md. Mosaddek Khan
Moumita Choudhury
Long Tran-Thanh
Nicholas R. Jennings

Distributed Constraint Optimization Problems (DCOPs) are an important framework for modeling coordinated decision-making problems in multi-agent systems with a set of discrete variables. Later works have extended DCOPs to model problems with a set of continuous variables, named Functional DCOPs (F-DCOPs). In this paper, we combine both of these frameworks into the Mixed Integer Functional DCOP (MIF-DCOP) framework that can deal with problems regardless of their variables' type. We then propose a novel algorithm - Distributed Parallel Simulated Annealing (DPSA), where agents cooperatively learn the optimal parameter configuration for the algorithm while also solving the given problem using the learned knowledge. Finally, we empirically evaluate our approach in DCOP, F-DCOP, and MIF-DCOP settings and show that DPSA produces solutions of significantly better quality than the state-of-the-art non-exact algorithms in their corresponding settings.

PDF Details DOI

AAMAS Conference 2018 Conference Paper

A Generic Domain Pruning Technique for GDL-Based DCOP Algorithms in Cooperative Multi-Agent Systems

Md. Mosaddek Khan
Long Tran-Thanh
Nicholas R. Jennings

Generalized Distributive Law (GDL) based message passing algorithms, such as Max-Sum and Bounded Max-Sum, are often used to solve distributed constraint optimization problems in cooperative multi-agent systems (MAS). However, scalability becomes a challenge when these algorithms have to deal with constraint functions with high arity or variables with a large domain size. In either case, the ensuing exponential growth of search space can make such algorithms computationally infeasible in practice. To address this issue, we develop a generic domain pruning technique that enables these algorithms to be effectively applied to larger and more complex problems. We theoretically prove that the pruned search space obtained by our approach does not affect the outcome of the algorithms. Moreover, our empirical evaluation illustrates a significant reduction of the search space, ranging from 33% to 81%, without affecting the solution quality of the algorithms, compared to the state-of-the-art.

PDF

AAMAS Conference 2018 Conference Paper

A Near-Optimal Node-to-Agent Mapping Heuristic for GDL-Based DCOP Algorithms in Multi-Agent Systems

Md. Mosaddek Khan
Long Tran-Thanh
William Yeoh
Nicholas R. Jennings

Distributed Constraint Optimization Problems (DCOPs) can be used to model a number of multi-agent coordination problems. The conventional DCOP model assumes that the subproblem that each agent is responsible for (i. e. the mapping of nodes in the constraint graph to agents) is part of the model description. While this assumption is often reasonable, there are many applications where there is some flexibility in making this assignment. In this paper, we focus on this gap and make the following contributions: (1) We formulate this problem as an optimization problem, where the goal is to find an assignment that minimizes the completion time of the DCOP algorithm (e. g. Action-GDL or Max-Sum) that operates on this mapping. (2) We propose a novel heuristic, called MNA, that can be executed in a centralized or decentralized manner. (3) Our empirical evaluation illustrates a substantial reduction in completion time, ranging from 16% to 40%, without affecting the solution quality of the algorithms, compared to the current state of the art. In addition, we observe empirically that the completion time obtained from our approach is near-optimal; it never exceeds more than 10% of what can be achieved from the optimal node-to-agent mapping.

PDF