Source

papl / src / PaplSBL.mli

Full commit
(*
  Copyright (c) 2012 Anders Lau Olsen.
  See LICENSE file for terms and conditions.
*)
(** SBL planners
*)

type 'a pair_t = 'a * 'a

type kind_t = Standard | NonTransfer

module type SETUP = sig
  type t
  (** Search trees. *)

  type q_t
  (** Configurations. *)

  type value_t
  (** The type of value stored in the nodes of the search tree.
  *)

  type node_t = value_t PaplDLTree.node
  (** Tree nodes. *)

  val expand : t -> node_t option
  (** Search tree expansion function.

      [expand s] adds zero or more new nodes to the tree. The method either
      returns a single node [Some node] that other trees can connect to or
      [None] if no such connection should be attempted.
  *)

  val connect : t -> q_t -> node_t option
  (** Search tree connection function.

      [connect s q] attempts to reach [q] from the search tree [s]. If [q] is
      reached the function returns a node [Some node] of [s] such that the
      movement from [node] to [q] is valid. Otherwise the functions return
      [None].
  *)

  val remove_enum : t -> node_t BatEnum.t -> unit
  (** Prepare a set of nodes for removal from the tree.

      The function removes the nodes from any lookup tables or other internal
      structures of the search tree state but does not actually detach the nodes
      from their parents.
  *)

  val add : t -> node_t -> q_t -> PaplIncrConstraint.t -> node_t
  (** Add a node to a search tree.

      [node = add s parent q ec] is a new node of [s] with parent [parent] that
      contains a configuration [q] and has a edge constraint [ec] with respect
      to the movement to the parent.
  *)

  val get_q : value_t -> q_t
  (** The configuration stored in a node value. *)

  val get_ec : value_t -> PaplIncrConstraint.t ref
  (** Reference to the edge constraint stored in a node value. *)

  val make_constr : (q_t * q_t) -> PaplIncrConstraint.t
  (** Construct an incremental edge constraint for the movement that connects a
      pair of configurations.
  *)

  val kind : kind_t
  (** The style of SBL search tree to construct.

      [kind = Standard] means vanilla SBL.

      [kind = NonTransfer] means that nodes of this search tree are never
      transferred to other trees. If an edge turns out to be rejected, the
      entire tree connected by the edge is simply erased.
  *)
end

module type SETUP_PAIR = sig
  type q_t
  module Fst : SETUP with type q_t = q_t
  module Snd : SETUP with type q_t = q_t
end

module MakeBidir (A : SETUP) (B : SETUP with type q_t = A.q_t) :
  PaplPlanner.S
  with type q_t = A.q_t
  and type target_t = A.t * B.t

module MakeBidir1 (S : SETUP) :
  PaplPlanner.S
  with type q_t = S.q_t
  and type target_t = S.t * S.t

module MakeBidirPair (S : SETUP_PAIR) :
  PaplPlanner.S
  with type q_t = S.q_t
  and type target_t = S.Fst.t * S.Snd.t

module BruteForce : sig

  module type SETUP = sig
    include SETUP

    val add_root : t -> q_t -> node_t
    (** Add a root to a search tree.

        The node [root = add_root s q] is a new root node of [s] containing the
        value [q].
    *)

    val create : ?callback:(t -> unit) -> unit -> t
    (** Construct a search tree.

        The search tree [s = create ~callback ()] calls [callback] every time
        [expand s] is being called.
    *)

    val create_point : q_t -> t
    (** Construct a search tree for a point target.

        The search tree [s = create_point q] contains a single root node with
        the value [q].
    *)

    val create_region : q_t PaplPlanner.region_t -> t
    (** Construct a search tree for a region target.

        The search tree [s = create_region region] samples [region] every time
        [expand s] is being called and inserts the resulting configurations as
        root nodes of [s].
    *)

    val get_roots : t -> node_t BatEnum.t
    (** Enumeration of all root nodes of the search tree. *)
  end

  module type SETUP_PAIR = sig
    type q_t
    module Fst : SETUP with type q_t = q_t
    module Snd : SETUP with type q_t = q_t
  end

  module MakePointBidirPair (M : SETUP_PAIR) :
    PaplPlanner.POINT with type q_t = M.q_t

  module MakeSamplerBidirPair (M : SETUP_PAIR) :
    PaplPlanner.SAMPLER with type q_t = M.q_t

  module Unbiased : sig
    module type BF_SETUP = sig
      type q_t
      val make_constr : (q_t * q_t) -> PaplIncrConstraint.t
      val connect_dist : q_t PaplMetric.option_t
      val connect_constr : q_t PaplEdgeConstraint.t option
      val expand : q_t -> q_t list
      val kind : kind_t
      val rng : PaplRandom.rng_t
    end

    module MakeSetup (M : BF_SETUP) : SETUP with type q_t = M.q_t

    module MakePointBidir
      (SA : BF_SETUP)
      (SB : BF_SETUP with type q_t = SA.q_t) :
      PaplPlanner.POINT with type q_t = SA.q_t

    module MakePointBidir1 (S : BF_SETUP) :
      PaplPlanner.POINT with type q_t = S.q_t

    module MakeSamplerBidir
      (SA : BF_SETUP)
      (SB : BF_SETUP with type q_t = SA.q_t) :
      PaplPlanner.SAMPLER with type q_t = SA.q_t

    module MakeSamplerBidir1 (S : BF_SETUP) :
      PaplPlanner.SAMPLER with type q_t = S.q_t
  end

  module RRT : sig
    module type BF_SETUP = sig
      type q_t
      val make_constr : (q_t * q_t) -> PaplIncrConstraint.t
      val connect_dist : q_t PaplMetric.option_t
      val connect_constr : q_t PaplEdgeConstraint.t option
      val expand_dist : q_t PaplMetric.option_t
      val expand_constr : q_t PaplEdgeConstraint.t option
      val expand : q_t -> q_t -> q_t list
      val sampler : q_t option PaplSampler.t
      val kind : kind_t
    end

    module type BF_SETUP_PAIR = sig
      type q_t
      val make_constr : ((q_t * q_t) -> PaplIncrConstraint.t) pair_t
      val connect_dist : q_t PaplMetric.option_t pair_t
      val connect_constr : q_t PaplEdgeConstraint.t option pair_t
      val expand_dist : q_t PaplMetric.option_t pair_t
      val expand_constr : q_t PaplEdgeConstraint.t option pair_t
      val expand : (q_t -> q_t -> q_t list) pair_t
      val sampler : q_t option PaplSampler.t pair_t
      val kind : kind_t pair_t
    end

    module MakeSetup (M : BF_SETUP) : SETUP with type q_t = M.q_t

    module MakeSetupPair (M : BF_SETUP_PAIR) :
      SETUP_PAIR with type q_t = M.q_t
      
    module MakePointBidir
      (A : BF_SETUP)
      (B : BF_SETUP with type q_t = A.q_t) :
      PaplPlanner.POINT with type q_t = A.q_t

    module MakePointBidir1 (S : BF_SETUP) :
      PaplPlanner.POINT with type q_t = S.q_t

    module MakeSamplerBidir
      (A : BF_SETUP)
      (B : BF_SETUP with type q_t = A.q_t) :
      PaplPlanner.SAMPLER with type q_t = A.q_t

    module MakeSamplerBidir1 (S : BF_SETUP) :
      PaplPlanner.SAMPLER with type q_t = S.q_t

    module MakePointBidirPair (M : BF_SETUP_PAIR) :
      PaplPlanner.POINT with type q_t = M.q_t

    module MakeSamplerBidirPair (M : BF_SETUP_PAIR) :
      PaplPlanner.SAMPLER with type q_t = M.q_t
  end
end