welcome: please sign in

Revision 1 as of 2011-01-21 10:44:17

Clear message
location: FinalProblemDescriptions / PartnerUnitsPolynomial

Partner Units Polynomial

Contents

  1. Partner Units Polynomial
    1. Problem Description
    2. Predicates
    3. Input format
    4. Output format
    5. Example(s)
    6. Author(s)

Problem Description

A given people counting system includes three types of components, namely door sensor, zone, and communication unit. The problem requirements are:

  1. Each zone as well as each door sensor must be connected to exactly one unit;
  2. Each unit can control at most two door sensors and at most two zones;
  3. If a unit controls a door sensor that contributes to a zone controlled by another unit, then the two units must be connected directly, i.e. one unit becomes a partner unit of the other and vice versa;
  4. Each unit can have at most two partner units.

The solution of the partner unit problem is defined as follows: Given a consistent configuration of door sensors and zones (encoded in the binary predicate zone2sensor/2) and a set of available units (comUnit/1), a maximum number of allowed partnerunits(maxPU/1), equal to two in this case, find a valid assignment of units that satisfies all requirements.

Predicates

Input format

The predicates comUnit/1 and maxPU/1 define available units and the number of allowed partner units respectively. The fact that a door sensor belongs to a zone is given by means of zone2sensor/2 predicate, e.g. zone2sensor(1,1) means that doorSensor(1) belongs to zone(1).

Output format

A solution to the problem is an assignment of each zone and each sensor to a unit, e.g. unit2sensor(2,1), unit2zone(2,1) means that zone(1) and doorSensor(1) are assigned to the second unit comUnit(2). Connections between partner units are given by the partnerunits/2 predicate, e.g. partnerunits(2,1) indicates a connection between comUnit(2) and comUnit(1).

Example(s)

Author(s)