| ||||||
SORAL is the SARBayes Optimal Resource Allocation Library, a programmer's API of optimization algorithms tailored to Search And Rescue (SAR). From an end-user's perspective, SORAL provides functions to best allocate a given set of SAR resources to most effectively find a lost person. The SORAL API is a simple, clean, modular collection of algorithms, each of which is optimal in its own domain. By virtue of plugging in to SORAL, each also provides important values for the end-user, such as probability of detection, coverage, and others.
SORAL is free (libre) software available under the GNU General Public License (GPL). Unless you secure a separate license, this requires any software which uses SORAL to also be GPL. In order to ensure that using SORAL will not adversely affect the licensing status of your own software, please see the the file COPYING for the full text of the GPL.
If there is possibility of a conflict please contact the SARBayes group or Monash University to negotiate a separate license. We have reasonable terms, because we want SORAL to be used.
The SARBayes project is based at Monash University (Australia), the web site is at: http://sarbayes.org/ SORAL was officially released mid-May, 2003. The most recent documentation and information is available at the web site.
Each area on the map has a probability of containing the missing person or object (the subject), normally called the Probability of Area (POA) or Probability of Containment (POC). After searching an area (and not finding anything) the probability of the subject being in that area is reduced: we are more confident they are not there. As we can never be completely certain we didn't miss subject during the search, these probabilities will approach, but never actually reach zero. A theoretically optimal allocation is one that tries to minimize the search time, that is to assign resources to areas where they will be most effective in lowering the total probability that the subject is in one of the search areas.
Both the resource and area data must be provided to SORAL (see ). SORAL uses this data and one of a number of allocation algorithms (you choose which) to create a set of allocations. An allocation tells you an area to be searched, a resource to search it, and the amount of time (effort) that resource should spend there. Each set of allocations is for a given operational period (batch of sorties) and SORAL will normally assign all the resource hours you give it. Normally in a search you will call SORAL repeatedly, at least once per operational period.
For details of those people and organisations assisting the project please see http://www.sarbayes.org/credit.shtml
SORAL is an ongoing project, but with a stable interface. This means if you build your system to work with SORAL now, you should (with very little work on your part) get improved resource allocation algorithms as SORAL develops in the future. Perhaps best of all, you can build resource allocation into your software without having to worry about the actual search theory. SORAL encapsulates the theory so all you need to handle are the inputs and resulting allocations.
Note: While SORAL is in Beta, the interface may change slightly. But it is largely stable.
numRes: An int. This is the total number of resources.numAreas: An int. This is the total number of areas.effectiveness: An Array2D. This is the effectiveness matrix, see below.availHours: A valarray of doubles. The ith member of the array corresponds to the number of hours available for the ith resource. (In SORAL you may use any consistent set of units, so this does not have to be in hours.)POA: A valarray of doubles. The ith member of the array corresponds to the POA for the ith area.You may name them whatever you want, but they must have these types.
ActiveArea wraps an area number. It provides:int getActiveAreaNum() constAreaAssignment wraps an area number and a time. It provides:int getAreaNum() constdouble getTime() constint getResourceNum() constdouble getTime() const
To make a Washburn allocation object called theAllocation, you would call:
Washburn theAllocation (numRes, numAreas, effectiveness, availHours, POA);
You then access the result allocations through iterators. The standard iterator paradigm is:
Let's explain this in some detail, and then see a simple example that puts it all together in a simple print routine.
++ operator. You can extract the current ActiveArea with the * operator. (An ActiveArea contains an area number as an integer, accessed with getActiveAreaNum().ActiveAreasIterator activeItr(theAllocation);
areaIndex. You can move the iterator to the next resource (in this area) with the ++ operator. You can extract the current ResourceAssignment with the * operator. (A ResourceAssignment contains a resource number and a time, accessed with getResourceNum() and getTime().)ResourceIterator resItr(theAllocation, areaIndex);
ResourceAssignment resAssign(*resItr); // get current object int resIndex (resAssign.getResourceNum()); // extract resource num double time (resAssign.getTime()); // extract time ++resItr; // move on to next
++ operators on your ResourceIterator and your ActiveAreasIterator as appropriate. Remember: always check whether the iterator is atEnd() before trying to read from it!sample.cpp
void printAssignments(const Allocation& theAllocation)
{
ActiveAreasIterator activeItr(theAllocation);
// While there are still areas with assignments
while(!(activeItr.atEnd()))
{
ActiveArea area(*activeItr);
int areaIndex(area.getActiveAreaNum());
ResourceIterator resItr(theAllocation, areaIndex);
// While there are still resources in this area
while (!(resItr.atEnd()))
{
ResourceAssignment resAssign(*resItr);
int resIndex (resAssign.getResourceNum());
double time (resAssign.getTime());
cout << " Area: " << areaIndex
<< " Resource: " << resIndex
<< " Time: " << time << endl;
++resItr;
}
++activeItr;
}
}
That's all there is to it. As an exercise, rewrite the loop using an AreaIterator.
Remember: The resource numbers and area numbers you get out of SORAL will not necessarily correspond to the numbers the user, or your program, use! SORAL's indices are relative to the area / resource position in the valarray and effectiveness matrix, so the first probability in the POA vector will be POA for the area with index 0. SORAL knows only how many areas and how many resources, and numbers them 0..n-1. You are responsible for translating them back to your own numbers! In particular, we have no way of knowing which resources you gave us, especially as your resource list will be changing over time.
POA and availHours are valarrays of doubles. Valarrays are built-in C++ types which act like vectors but are not resizeable and are very fast.The ordering of areas and resources is not important, but it must be consistent between these valarrays and the effectiveness matrix. The position in the valarray will also be the index used by the SORAL iterators so you will need to convert this back to your own indices or names when copying the data back.
Remember: SORAL does not care what your areas or resources are called, or which ones you gave it. SORAL cares only that there are n areas and m resources, and numbers them 0..n-1 and 0..m-1. Do not mistake the iterator's area or resource number as your own internal number (unless your areas and resources happen to be numbered from 0, and happen to have been passed into SORAL in the correct order).
The effectiveness matrix is of type Array2D. This is a custom data type to SORAL and allows matrix-style data access to a dynamically created data structure. The values in the structure are stored as doubles. To create an Array2D you pass in the number of areas and the number of resources.
Example:
Array2D effectiveness = Array2D(numAreas, numRes);
You can access a member of the array as shown below.
Example:
effectiveness[i][j]=3.14127;
where:
where both (Effective Sweep Width) and speed are for that resource in that area.
It is convenient to denote these values more briefly as:
How you approximate is up to you, but as the accuracy of the algorithms crucially depend on these values, please look for recent publications or reports in the area. We hope to make some tables and functions available ourselves. In the meantime, here is a suggestion:
For each resource, attempt to measure a sweep width in some kind of standard conditions, perhaps a flat open field. Then fill in other values via correction factors.
The creation of useful effectiveness values is an ongoing research task. SARBayes will hopefully develop methods and tools for dealing with this problem in the future. Please ask us what we know about the most recent research.
sample.cpp shows how to include the necessary headers, create values, and call SORAL.
#include <iostream>
#include <vector>
#include "containr.h"
#include "Allocatn.h"
#include "Array2D.h"
#include "Alloc-W.h"
#include "Alloc-CC.h"
#include "UserDef.h"
using namespace std;
// function definitions
void printAssignments(const Allocation& theAllocation);
int main()
{
int num_areas = 2;
int num_resources = 2;
Array2D effectiveness(num_areas, num_resources);
valarray<double> availableHours(num_resources);
valarray<double> POA(num_areas);
// Fill in the effectiveness matrix
effectiveness[0][0] = 1.0;
effectiveness[0][1] = 5.0;
effectiveness[1][0] = 0.2;
effectiveness[1][1] = 0.05;
// Add each resource's avail. time to the availableHours valarray
availableHours[0] = 161;
availableHours[1] = 139;
// Add each area's initial probability to the POA valarray
// Values don't have to be normalized.
POA[0] = 0.5;
POA[1] = 0.5;
// Run the allocation. This one has 2 resources and
// a non-trivial effectiveness table, so it requires
// the Washburn algorithm to get the right answer.
Washburn theAllocation (num_resources,
num_areas,
effectiveness,
availableHours,
POA);
// Now display results
cout << "The calculated allocation\n";
printAssignments(theAllocation);
return 1;
}
The printAssignments routine was shown in Iterators Example.
For this to work your ground searchers should have similar effectiveness.
Once we're done with the basic documentation and bug fixes, we'll implement a heuristic search based on Washburn that assumes it cannot split the resources. That is the more usual situation for search managers.
Like any other allocation, you can get the Coverage, POD, POS, and other statistics for UserDef. Thus, you can tweak a Washburn allocation to fit your constraints, and see how close you are to optimal.
Example
If you already have an allocation (from the previous example), you can change it to UserDef and then modify it as shown here. This code is taken from sample.cpp, where you may see it in context.
// Here's how to convert to a UserDef allocation UserDef changedAllocation(theAllocation); // Perform the tweak. Remove 5 hours from resource 0 // in area 0. changedAllocation.remove(1,0,5);
UserDef allows entire assignments to be deleted and created, as well as altered. UserDef does some bookkeeping for you, keeping a pool of unallocated resources, which you can re-add to an area with the "add" function. Note that this lets you create an allocation that does not use all your resources. Usually, you don't want to do that, so we have provided the calls:
bool haveUnallocatedResources().valarray<double> getUnallocatedResources().Until we write more here, see the source code documentation for the various operations provided by UserDef.
We maybe should tell you more about resource allocation in general, or about the particular algorithms. Or perhaps leave that for a theory paper rather than an API User's Guide.
And we should tell you about all the neat functions in Allocation:
But in the meantime, you should find that the source-code documentation tells you quite a bit about them and how to use them.
Use the source, Luke!
| (SARBayes) | Main | Related Pages | Class List | Hierarchy | Methods | Files |
|---|