Enhancing Multi-Criteria Decision-Making: A Novel Approach to Generalized Decision Rules Using Mahalanobis Distance
Enhancing Multi-Criteria Decision-Making: A Novel Approach to Generalized Decision Rules Using Mahalanobis Distance
Abstract
This paper introduces the Modified Generalized Decision Rules (MaGDR) algorithm, an enhancement of the traditional Generalized Decision Rules (GDR) algorithm, which integrates the Mahalanobis distance to address inherent limitations in multi-criteria decision-making (MCDM). Traditional GDR algorithms often struggle with correlation and scaling issues among different criteria, leading to suboptimal decision-making. By incorporating the Mahalanobis distance, the MaGDR algorithm provides a robust, scale-invariant method that accurately reflects true distances within the criteria space, thus improving decision-making accuracy and reliability. We detail the theoretical modifications to the GDR algorithm, emphasizing the computational mechanics and integration of the Mahalanobis distance. The implementation is demonstrated through a simulation of robotic pathfinding, a complex decision-making scenario characterized by obstacle avoidance. The simulation results validate the MaGDR algorithm's enhanced capability to handle intricate pathfinding tasks, showing improvements in decision-making efficiency compared to the Dijkstra algorithm. The findings suggest that the MaGDR algorithm not only performs effectively in typical MCDM applications but also excels in scenarios requiring nuanced assessments of multiple conflicting criteria. Future researches will explore the scalability of this approach in other domains, such as healthcare and logistics, and seek to optimize iteration efficiency further.
1. Introduction
Multi-Criteria Decision-Making (MCDM) is considered as a field in operations research, management science, and multiagent systems, addressing problems where decisions must be made in the presence of trade-offs between two or more conflicting criteria. In various fields such as engineering, finance, healthcare, and environmental planning, MCDM facilitates the evaluation and comparison of different options based on a set of criteria rather than a single criterion , , . For example, in autonomous vehicles navigation system is modelled as a multiagent system, MCDM is used to balance trade-offs between minimizing travel time, reducing energy consumption, and maximizing passenger safety. All of them are influenced by different environmental and traffic conditions. One of the critical challenges in MCDM is to accurately synthesize and prioritize diverse sets of criteria to make a decision that aligns with strategic objectives and operational frameworks.
The Generalized Decision Rules (GDR) algorithm is a robust tool within MCDM techniques, particularly valuable in complex decision support systems. GDR applies a set of rules that systematically evaluate each option against all criteria. These rules typically involve aggregating individual criteria scores through various metrics, such as calculating sums, maximums, and distances to the ideal point, which are used to rank or select the best alternatives . Although, the GDR is effective in many scenarios, it often fails to account for the correlation and relative scaling among criteria. That can lead to suboptimal decision-making when cope with criteria that are interdependent or varying units and scales.
Recognizing the limitations inherent in the traditional GDR algorithm, there is a need to enhance its methodology to incorporate more sophisticated measures that respect the statistical properties of the criteria space. To address these challenges, an integration of the Mahalanobis distance concept into GDR represents a significant advancement in this direction. The Mahalanobis distance, unlike simpler distance measures, considers the covariance among the criteria, so providing a more accurate reflection of the true distances within the criteria space, factoring in correlations and variances that are critical in many decision-making contexts . By considering the Mahalanobis distance concept, the modified GDR algorithm not only respects the multidimensional nature of the decision space but also adjusts for any disproportionate influence of widely varying scales among the criteria.
This paper introduces a novel adaptation of the GDR algorithm that leverages the Mahalanobis distance to improve decision-making accuracy and reliability. That addresses the limitations of traditional GDR by enhancing its capability to process complex, multidimensional space in a way that is both scale-invariant and sensitive to the inherent correlations among decision criteria. This modified approach promises to refine decision support systems by offering a method that is not only theoretically sound, but also practically more effective in dealing with multi-criteria decision problems.
The following sections details the theoretical background of this modified algorithm, describe the methodological innovations, present empirical evidence by applying it to a pathfinding problem in robotics to validate the approach and discuss the potential implications of the findings.
2. Methodology
This section outlines the foundational principles of the GDR algorithm, the integration of the Mahalanobis distance, and the solutions to computational issues like covariance matrix singularity.
2.1. The Original GDR Algorithm
The GDR algorithm utilizes a structured decision-making data, defined by a set of options and criteria
. The necessary conditions that are required for effective GDR algorithm:
1. Homogeneity of Criteria.
Within the vector objective function (VTF), all criteria must uniformly adopt an extremum type, either minimized or maximized, to ensure consistency. The selection of this extremum type is important as it determines the metrics subsequently used within the algorithm. The mathematical representation of this concept is shown in Equation 1 and 2.
If the VTF includes a mix of maximized and minimized criteria. Then modifications are necessary to standardize the extremum type across all criteria. For example, if the goal is to convert the criterion extremum from minimum to the form of maximized ones. There are two main approaches to achieve that:
One approach involves calculating inverse values, specifically by raising the initial minimized values to the power of (-1).
Another approach is to determine some suitable constant and replace the minimized criterion under consideration with the maximized criterion
2. Commensurability of Criteria: All criteria should have the same unit of measurement.
3. Scaling: All criteria must be normalized to the same scale, allowing for direct comparisons.
2.2. GDR algorithm metrics and steps
The following steps is used to prepare the dataset for the calculation of decision metrics. Upon establishing the set of options and criteria
, the next phase involves normalizing the criteria using Equation 3 to ensure a uniform scale, followed by applying weights W as in Equation 4 to adjust the influence of each criterion according to its perceived importance.
2.3. Decision Metrics Explanation
This step includes calculating three primary metrics for each option to facilitate evaluation and comparison:
- SUM/MINSUM or SUM/MAXSUM: This metric sums all criteria for an option, normalized against the minimum or maximum sum across all options, respectively in Equation 5 and 6.
- MAX/MINMAX or MIN/MAXMIN: The maximum value among criteria for an option, normalized by the minimum maximum across options. Or the minimum value among criteria for an option, normalized by the maximum minimum across options. Respectively in Equation 7 and 8.
- DTI/MINDTI or DTI/MAXDTI: Measures the Euclidean distance to an ideal point, normalized by the minimum or maximum distance across options, respectively, offering a sense of how each option deviates from an idealized points as in Equation 9 and 10.
2.4. Iterative Selection
Figure 1 - GDR flowchart
In general, GDR algorithm is robust, although it presents certain limitations that can reduce its reliability in complex decision-making scenarios. Notably, these limitations include issues such as the potential for division by zero in distance calculations, the lack of uniformity in unit measurement across criteria, and the consequent need for normalization. These limitations highlight the necessity for methodological enhancements to improve the algorithm’s adaptability and accuracy.
2.6. Addressing Division by Zero in GDR
A significant computational challenge within the GDR occurs when calculating the normalized distances, particularly when the minimum distance metric equals zero, leading to division by zero errors. This issue arises in scenarios where an option perfectly matches the ideal or reference point, making the denominator in the DTI/MINDTI normalized metric calculation zero. To circumvent this problem, our modification introduces a break in the iteration process whenever this condition is encountered, automatically selecting that option as the optimal choice. This approach not only resolves the division by zero issue but also streamlines the decision-making process by promptly identifying the most suitable option.
2.7. Incorporating Mahalanobis Distance into GDR
The Mahalanobis distance offers a more sophisticated alternative to the traditional Euclidean distance. Unlike Euclidean distance, which measures straight-line distance irrespective of data distribution, the Mahalanobis distance takes into account the variance-covariance structure of the data. The use of Mahalanobis distance does not necessitate the normalization or standardization of data across different units of measurement, as it inherently adjusts for scale differences and correlations through its reliance on the covariance matrix. This makes it particularly useful in multivariate settings where variables may not be on the same scale. Thus, it provides a robust, scale-invariant method for measuring distances that reflect the underlying relationships within the data.
Where:
: The value of option for criterion j.
The ideal point (Minimum point/Maximum point)
С: The covariance matrix.
2.8. Handling Covariance Matrix Singularity
The issue in calculating Mahalanobis distance is the singularity of the covariance matrix, particularly when the data points are collinear or the number of criteria exceeds the number of options. A singular matrix is non-invertible, which prevent the computation of Mahalanobis distance. To tackle this, the solution involves employing the pseudoinverse of the covariance matrix rather than its traditional inverse. The pseudoinverse, generally calculated using methods such as the Moore-Penrose algorithm, offers a robust alternative that effectively handles cases where the matrix may not be directly invertible .
2.9. Implementation of the Modified GDR (MaGDR) Algorithm
The implementation of MaGDR algorithm incorporates the Mahalanobis distance to enhance the decision-making process, specifically designed to overcome the limitations identified in traditional GDR.
Setup and Steps
1. Data Collection and Pre-processing:
- Gather all relevant data required for the decision-making process, ensuring comprehensive coverage of options and criteria.
- Define the set of options and criteria
- Optionally Apply weights W as in Equation 12, omitting normalization to maintain the original units of measurement.
2. Computation of Decision Metrics:
- SUM/MINSUM or SUM/MAXSUM
- MAX/MINMAX or MIN/MAXMIN
- DTI/MINDTI or DTI/MAXDTI
Applying Mahalanobis distance to calculate DTI metric:
- Calculate the covariance matrix for the criteria or metrics set. This matrix will reflect the variance and covariance.
- In cases where the covariance matrix is singular, employ the pseudoinverse technique to preserve its usability for the calculations.
- For each option, compute the Mahalanobis distance as in Equation 11 from the option to the ideal point. This step requires the inversion or pseudoinversion of the covariance matrix that calculated previously.
3. Iterative Selection Process:
- Apply the iterative selection process where option that meet the condition of all its metrics equaling 1 is selected.
- This iterative process systematically refines the set of options, methodically filtering from the most to the least suitable choices.
2.10. Application of MaGDR in Robotics Pathfinding
Pathfinding in robotics fundamentally involves complex decision-making, where the goal is to determine the best route from a starting point to a destination in an environment with potential obstacles. Efficient and safe navigation is critical in various robotics sectors, such as autonomous vehicles, automated warehousing, and rescue operations. Robotic pathfinding reflects MCDM challenges, including dynamic obstacle avoidance, travel distance optimization, energy consumption minimization, and strict adherence to safety protocols. Each route must be evaluated on multiple criteria that often conflict . The MaGDR algorithm offers a sophisticated method to address this multi-dimensional evaluation. The primary objective of this simulation is to verify and validate the MaGDR algorithm's decision-making capabilities in complex environments.
2.11. Simulation Setup
The simulation of the MaGDR and Dijkstra algorithms is conducted within a controlled virtual environment. The primary tools utilized include the Python programming language , supplemented by essential libraries such as Matplotlib for visualization, NumPy for numerical operations, and pandas for data manipulation. The environment is set up to mimic a two-dimensional space with various obstacles.
2.12. Motion Model Description
The motion model is formulated by the possible movements the robot can take through the grid. It is defined by a set of tuples representing the movement cost and energy consumption associated with each movement direction [x, y] as in Table 1. The values in table 1 were selected experimentally to reflect the MCDM problem.
Table 1 - Motion model
Direction [x, y] | Energy Consumption | Movement Cost |
Right [1, 0] | 1 | 1 |
Left [-1, 0] | 1.2 | 1 |
Up [0, 1] | 1.1 | 1 |
Down [0, -1] | 1.3 | 1 |
Top-right [1, 1] | 1.9 | 0.5 |
Top-left [-1, 1] | 1.7 | 0.5 |
Bottom-right [1, -1] | 1.8 | 0.5 |
Bottom-left [-1, -1] | 1.6 | 0.5 |
2.13. MaGDR Criteria and weights
The set of options (Nodes in search space) and Criteria (Movement cost, Euclidean distance to the goal, Energy) was created for every step of the robot towards the goal. Weights were assigned experimentally as [0.1, 0.7, 0.2]; varying these values could yield different results.
3. Results and Analysis
In evaluating the performance of the MaGDR and Dijkstra algorithms, the metrics used are as follows:
1. Path Length: This metric measures the total nodes covered by the path selected by each algorithm from the start to the goal node.
2. Energy Consumption: Reflecting the cumulative energy cost associated with the entire path.
3. Movement Cost: This is the cumulative cost along the selected path.
Figure 2 - MaGDR selected path
Figure 3 - Dijkstra selected path
Table 2 - Performance Metrics Comparison
Metric | MaGDR | Dijkstra |
Path Length (nodes) | 52 | 52 |
Energy Consumption | 93.8 | 79.8 |
Movement Cost | 27 | 37 |
Number of Visited Nodes | 705 | 1230 |
1. Path Length: Both algorithms identified paths comprising 52 nodes, indicating an equality in terms of the shortest path capability under the tested conditions.
2. Energy Consumption: MaGDR recorded a higher energy consumption of 93.8 compared to 79.8 by Dijkstra. Notably MaGDR prioritize the shorter paths based on the value of weight (user preferences).
3. Movement Cost: Dijkstra's path had a higher cumulative cost of 37, compared to 27 by MaGDR. This proves that MaGDR is more cost-efficient based on the selected parameters.
4. Number of Visited Nodes: Dijkstra explored a larger search space with 1230 nodes visited, significantly more than the 705 by MaGDR. This indicates that MaGDR is more decision-making efficient, evaluating fewer nodes before concluding the path planning.
4. Conclusion
The development and implementation of the MaGDR algorithm, incorporating the Mahalanobis distance, represents a significant advancement in the field of MCDM. This research demonstrates that the MaGDR algorithm provides a robust, scale-invariant method for evaluating complex decision-making scenarios. By addressing the inherent limitations of traditional GDR algorithms, particularly in handling correlations and scaling issues among different criteria, MaGDR offers more general uses. The application of the MaGDR algorithm in robotic pathfinding has verified its potential to improve decision-making efficiency. The simulation results clearly show that MaGDR can effectively navigate environments, optimize multiple conflicting criteria. Although MaGDR sometimes results in higher energy consumption, its ability to minimize movement costs and evaluate fewer nodes before reaching a decision underscore its efficacy in strategic pathfinding applications. Future research could further explore the scalability of MaGDR across other domains such as healthcare, environmental management, and logistics, where decision-making scenarios are complex.