aruspex

A configurable constraint solver

Monthly Downloads: 0

Programming language: Elixir

License: MIT License

Tags: Algorithms And Data Structures    

Latest version: v0.1

README

Aruspex

Aruspex is a configurable constraint solver, written purely in Elixir.

Aruspex does, or atleast has the capacity to, support multiple constraint problem satisfaction strategies. Because of this property it is theoretically capable of supporting various types of CSPs.

At the time of writing Aruspex ships with one strategy, simulated annealing, which supports weighted CSPs.

This readme refers to master, please check the readme for your release.

Example

Given a map of Australia, find some colouring of teritories, such that no adjacent territory has the same colour.

import Aruspex.Server
use Aruspex.Constraint

{:ok, problem} = start_link

variables = [
  wa  = :western_australia,
  nt  = :nothern_territory,
  q   = :queensland,
  sa  = :south_australia,
  nsw = :new_south_wales,
  v   = :victoria,
  t   = :tasmania
]

domain = [:red, :green, :blue]

Enum.map variables, &(variable problem, &1, domain)

problem
|> set_search_strategy(Aruspex.Strategy.SimulatedAnnealing)
# adjacent territories cannot be the same colour
# The pin operator is used to reference a named variable in a constraint,
# check the section on variables below.
|> post(linear ^wa != ^nt)
|> post(linear ^wa != ^sa)
|> post(linear ^sa != ^nt)
|> post(linear ^sa != ^q)
|> post(linear ^sa != ^nsw)
|> post(linear ^sa != ^v)
|> post(linear ^nt != ^q)
|> post(linear ^q != ^nsw)
|> post(linear ^nsw != ^v)
|> find_solution
|> IO.inspect
# [ new_south_wales:    :blue,
#   nothern_territory:  :blue,
#   queensland:         :green,
#   south_australia:    :red,
#   tasmania:           :green,
#   victoria:           :green,
#   western_australia:  :green ]

For some more examples checkout [these.](test/support/examples/)

Usage

Check the api exposed by Aruspex.Server

Creating a new problem

Aruspex uses a GenServer under the hood, to create a new problem simply use

{:ok, pid} = Aruspex.Server.start_link

Defining a new variable

A literal is used to name a new variable, and a domain is specified for the variable. This literal will be used to reference the variable later when defining constraints and will appear in the solution.

@spec variable(pid, Literals, Enum.t) :: pid
^pid = Aruspex.Server.variable(pid, :x, 1..100)

Defining a new constraint

Adding a new constraint is called posting a constraint. Posting a constraint requires specifying the variables that participate in the constraint, as well as a function the returns a cost when tested.

Strategies attempt to minimize the cost of all constraints, where a total cost of 0 would be a perfect solution.

all_diff/1

Constraints may be defined using built in constraints:

pid
|> post(all_diff [:x, :y])

The all_diff constraint would impose a condition that all variables specified must be unique.

linear/1

using the linear/{1,2} macro (only supports clauses that can be inlined - only expressions that can appear in guard clauses):

pid
|> post(linear ^:x == ^:y)

inside the body of the linear/1 macro pinned literals indicate that the value refers to a named variable which will be substituted in during compilation. pinned variables may also be used to the same effect.

unpinned values will be used by value.

some_var = :x
z = 1
pid
|> post(linear ^some_var == ^:y + z)

is equivalent to:

pid
|> post(linear ^:x == ^:y + 1)

linear/2

In it's second form, the named variables may be defined explicitly, and matched on.

pid
|> post(linear [:x, :y],
               [{x1, _}, {_, y2}] when x1 == y2)

constraint/1

User defined constraints are also supported by using the constraint record directly.

Strategies will test constraints by applying the values for variables, in the order specified, to function.

function must have a type of [Literals] -> number.

pid
|> post(constraint(
  variables: [:v, :w],
  function: fn ([v, w]) ->
    cond do
      v > 10 ->
        100
      w < 10 ->
        9999
      true ->
       0
    end
  end
))

Roadmap

• [ ] configurable settings for s.a. strategy (run time, cooling strategy, etc.)
• [ ] configurable tolerance for what is an acceptable solution (default is only perfect solutions)
• [ ] allow strategies to return multiple soltuions with message box.
• [ ] allow multiple strategies to be employed, which will act as middlewear.
• [ ] user defined optimization tolerance
• [ ] implement more common constraints from the global constraint catalog.
• [ ] add additional strategies