RTS2 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== GA Scheduling organization ======

Algorithm and ideas used for scheduling are described in [[http://rts2.org/scheduling.pdf|master thesis]]. Please read this carefully before you will try to add new code.

The algorithm mention constraints and objectives. Constrains method return number of constraint violations and the algorithm tries to minimize them, providing schedule with zero constraint violations. So far there are not soft and hard constraint, and implementation of them to scheduling can be an interesting topics. The algorithm search for maximal values of the objective functions.

Important is to remember that lower constraint violation value means better schedule, and higher objective function value means better schedule. If you come to objective which naturally produces better schedules when lower value is calculated, you can easily change function by using //1/f(x)// instead.

In order to use GA scheduling, you will need to fill in database. You will also find it useful to use //pyrts2// to visualise schedule, so you will be able to see how scheduling algorithm behaves.

===== Database setup =====

//Note: Currently you need to build database from REL_0_8_0 branch. See bellow how to retrieve it.//

You need to fill **tickets** and **accounts** tables.

**Tickets** table contains those fields:

^ Field name ^ Data type ^ Description ^
| schedticket_id     | integer                     | unique ID of ticket - primary key  |
| tar_id             | integer                     | ID of target which belongs to the ticket |
| account_id         | integer                     | ID of account - can be null if this ticket is out of accounting |
| obs_num            | integer                     | Maximal number of observations - scheduler will try to schedule only observations bellow this number |
| sched_from         | timestamp without time zone | Schedule observation from this time; if null, schedule anytime |
| sched_to           | timestamp without time zone | Schedule observation to this time; if null, schedule anytime |
| sched_interval_min | interval                    | Minimal interval between observations |
| sched_interval_max | interval       | Maximal interval between observations |

===== Using pyrts2 to preview schedules =====


====== Obtaining and modifying code ======

The GA scheduler code currently lives only in [[http://rts-2.svn.sf.net/viewvc/rts-2/branches/rts-2/REL_0_8_0|REL_0_8_0]] branch. Merging to trunk is expected in a few weeks. To get the code, issue:

<code bash>
svn co https://rts-2.svn.sf.net/svnroot/rts-2/branches/rts-2/REL_0_8_0
</code>

Most of functionality you are interested in is located in [[http://rts-2.svn.sf.net/viewvc/rts-2/branches/rts-2/REL_0_8_0/src/scheduler|src/scheduler]] directory. Here we will mention two changes you will most probably like to to - add a new merit, or new constraint.

===== Adding a new constraint =====

To add a new constraint, you should first declare its symbolic name in [[http://rts-2.svn.sf.net/viewvc/rts-2/branches/rts-2/REL_0_8_0/src/scheduler/rts2schedule.h|rts2schedule.h]]. The constraint shall be added to constraintFunc enumeration:

<code c++>

typedef enum
{
        CONSTR_VISIBILITY,                       // visibility violation - target is not visible
        CONSTR_SCHEDULE_TIME,            // schedule violation - target is scheduled outside its allowed time OR there exists target(s) which was not scheduled while it must be scheduled
        CONSTR_UNOBSERVED_TICKETS,       // number of unobserved tickets - tickets which have time constraint for schedule period, have some numObs left, but were not observed
        CONSTR_OBS_NUM                           // target is observed more times then it should be observed
} constraintFunc;
</code>

After you are done, you need to define function which will count constraint violation for you. And you will need to add it to //getConstraintFunction// method. Here is the example how **CONSTR_VISIBILITY** is defined. In [[http://rts-2.svn.sf.net/viewvc/rts-2/branches/rts-2/REL_0_8_0/src/scheduler/rts2schedule.h|rts2schedule.h]] you will find:

<code c++>
                /**
                 * Return constraint function. Constraint is satisfied, if return is = 0. Otherwise
                 * number of constraint violations is returned.
                 *
                 * @param _type Constraint function type.
                 *
                 * @return Number of targets which are infeasible with respect to given constraint.
                 */
                unsigned int getConstraintFunction (constraintFunc _type)
                {
                        switch (_type)
                        {
                                case CONSTR_VISIBILITY:
                                        visibilityRatio ();
                                        return unvisible;
                                case CONSTR_SCHEDULE_TIME:
                                        return violateSchedule ();
                                case CONSTR_UNOBSERVED_TICKETS:
                                        return unobservedSchedules ();
                                case CONSTR_OBS_NUM:
                                        return violatedObsNum ();
                        }
                        return UINT_MAX;
                }
</code>

and

<code c++>
                /**
                 * Ratio of observations from schedule which are visible.
                 *
                 * @return Ration of visible targets. Higher means better schedule.
                 */
                double visibilityRatio ();
</code>

and then in [[http://rts-2.svn.sf.net/viewvc/rts-2/branches/rts-2/REL_0_8_0/src/scheduler/rts2schedule.cpp|rts2schedule.cpp]] you will find that visibility constraint is calculated as:

<code c++>
double
Rts2Schedule::visibilityRatio ()
{
        if (!isnan (visRatio))
                return visRatio;

        visible = 0;
        unvisible = 0;

        for (Rts2Schedule::iterator iter = begin (); iter != end (); iter++)
        {
                if ((*iter)->isVisible ())
                        visible++;
                else
                        unvisible++;
        }
        visRatio = (double) visible / size ();
        return visRatio;
}
</code>

The most important is for you inner loop which calculated how much targets in the schedule are unvisible and visible. The first //if// is only syntax sugar for lazy initialization of values, which significantly improves scheduling algorithm speed. Important is iterator loop through members of the schedule, which ask every member if it is visible. //isVisible// is then defined in [[http://rts-2.svn.sf.net/viewvc/rts-2/branches/rts-2/REL_0_8_0/src/scheduler/rts2schedobs.h|rts2schedobs.h]] as:

<code c++>
                /**
                 * Determines schedule target visibility.
                 *
                 * @return True is observation is visible.
                 */
                bool isVisible ()
                {
                        // determine if target is visible during whole period
                        if (getTarget()->isGood (getJDStart ()) == false
                                || getTarget ()->isGood (getJDMid ()) == false
                                || getTarget ()->isGood (getJDEnd ()) == false)
                                return false;
                        double minA, maxA;
                        getTarget ()->getMinMaxAlt (getJDStart (), getJDEnd (), minA, maxA);
                        return minA > 0;
                }
</code>

For definition of //isGood// function, please have a look to [[http://rts-2.svn.sf.net/viewvc/rts-2/branches/rts-2/REL_0_8_0/src/utilsdb/target.ec|src/utilsdb/target.ec]].

After you are done, you shall add new constraint to constraint which will be used in scheduling. This is done in [[http://rts-2.svn.sf.net/viewvc/rts-2/branches/rts-2/REL_0_8_0/src/scheduler/rts2schedbag.cpp|rts2schedbag.cpp]]:

<code c++>
Rts2SchedBag::Rts2SchedBag (double _JDstart, double _JDend)
{
        // ommited lines..

        constraints.push_back (CONSTR_VISIBILITY);
        constraints.push_back (CONSTR_SCHEDULE_TIME);
        constraints.push_back (CONSTR_UNOBSERVED_TICKETS);
        constraints.push_back (CONSTR_OBS_NUM);
}
</code>

===== Adding new objective function =====

Process of adding new objective function is similar to adding new constraint. If you understand how constraint functions are added, you will not have any problems understanding how objectives are added.

You will need to add new objective symbolic name to objFunc enumeration. In [[http://rts-2.svn.sf.net/viewvc/rts-2/branches/rts-2/REL_0_8_0/src/scheduler/rts2schedule.cpp|rts2schedule.cpp]] you will need to add new objective to //getObjectiveName// function:

<code c++>
const char* getObjectiveName (objFunc obj)
{
        const static char* objNames[] = { "VISIBILITY", "ALTITUDE", "ACCOUNT", "DISTANCE",
                "DIVERSITY_TARGET", "DIVERSITY_OBSERVATIONS", "SINGLE"};
        return objNames[(int) obj];
}
</code>

Then procedure is similar - add objective to case in //Rts2Schedule::getObjectiveFunction//, add function to calculate it to //Rts2SchedObs// class.

And finally add it to //objectives// in [[http://rts-2.svn.sf.net/viewvc/rts-2/branches/rts-2/REL_0_8_0/src/scheduler/rts2schedbag.cpp|rts2schedbag.cpp]]:

<code c++>
        // fill in parameters for NSGA
        objectives.push_back (ALTITUDE);
        objectives.push_back (ACCOUNT);
        objectives.push_back (DISTANCE);
        objectives.push_back (DIVERSITY_TARGET);

</code>