14.21 stableMarriage

7PublicSchoolLads utilised a stable marriage algorithm approach to match important locations on the field to the available players in an globally optimal fashion. The idea was if we can define important formational locations on the field relative to the ball could we then optimally assign different players to go to those locations so that each location was allocated to a unique player in a way in which the overall distance traveled to get to those locations was minimized. In order to use this function though you need to first determine each players preference to for each position. This was handled in GeneratePreferenceArray

vector<int> NaoBehavior::stableMarriage(vector<vector<pair<double,int > > > PreferenceToPointArray)
{
    // Convert vector to 2D array
    int prefer[2*NUM_AGENTS][NUM_AGENTS];

    for(int i=0;i<NUM_AGENTS;i++){
        for(int j=0;j<NUM_AGENTS;j++){
            prefer[i][j] = PreferenceToPointArray[i][j].second;
            prefer[i+NUM_AGENTS][j] = j;
        }
    }
    
    // Stores partner of Points. This is our output array that
    // stores paring information.  The value of wPartner[i]
    // indicates the partner assigned to Point N+i.  Note that
    // the Points number between N and 2*N-1. The value -1
    // indicates that (N+i)'th point is free
    int wPartner[NUM_AGENTS];
  
    // An array to store availability of Players.  If mFree[i] is
    // false, then player 'i' is free, otherwise engaged.
    bool mFree[NUM_AGENTS];
  
    // Initialize all players and points as free
    memset(wPartner, -1, sizeof(wPartner));
    memset(mFree, false, sizeof(mFree));
    int freeCount = NUM_AGENTS;
  
    //for (int p=0;p<NUM_AGENTS;p++){
    //    cout << wPartner[p] << "\n";
    //}


    // While there are free players
    while (freeCount > 0)
    {
        // Pick the first free player (we could pick any)
        int m;
        for (m = 0; m < NUM_AGENTS; m++)
            if (mFree[m] == false)
                break;
  
        // One by one go to all points according to m's preferences.
        // Here m is the picked free player
        for (int i = 0; i < NUM_AGENTS && mFree[m] == false; i++)
        {
            int w = prefer[m][i];

            // The point of preference is free, w and m become
            // partners (Note that the partnership maybe changed
            // later). So we can say they are engaged not married

            if (wPartner[w] == -1)
            {
                wPartner[w] = m;
                mFree[m] = true;
                freeCount--;
            }
            else  // If w is not free
            {
                // Find current engagement of w
                int m1 = wPartner[w];
  
                // If w prefers m over her current engagement m1,
                // then break the engagement between w and m1 and
                // engage m with w.
                if (wPrefersM1OverM(prefer, w, m, m1) == false)
                {
                    wPartner[w] = m;
                    mFree[m] = true;
                    mFree[m1] = false;
                }
            } // End of Else
        } // End of the for loop that goes to all points in m's list
    } // End of main while loop
  
  
    // Print the solution
    /* cout << "Point   Player" << endl;
    for (int i = 0; i < NUM_AGENTS; i++)
       cout << " " << i << "\t" << wPartner[i] << endl; */


    vector<int> v(std::begin(wPartner), std::end(wPartner));
    return v;   
}