lbf/opt/
search.rs

1use crate::config::LBFConfig;
2use crate::opt::loss::LBFLoss;
3use crate::samplers::ls_sampler::LSSampler;
4use crate::samplers::uniform_rect_sampler::UniformRectSampler;
5use itertools::Itertools;
6use jagua_rs::collision_detection::CDEngine;
7use jagua_rs::collision_detection::hazards::filter::HazardFilter;
8use jagua_rs::entities::{Instance, Item};
9use jagua_rs::geometry::DTransformation;
10use jagua_rs::geometry::geo_traits::TransformableFrom;
11use log::debug;
12use ordered_float::OrderedFloat;
13use rand::Rng;
14use std::cmp::{Ordering, Reverse};
15
16/// Search the layout (i.e. CDE) for a valid placement of the item, with minimal loss.
17pub fn search(
18    cde: &CDEngine,
19    item: &Item,
20    config: &LBFConfig,
21    rng: &mut impl Rng,
22    sample_counter: &mut usize,
23    filter: &impl HazardFilter,
24) -> Option<(DTransformation, LBFLoss)> {
25    let surrogate = item.shape_cd.surrogate();
26    //create a clone of the shape which will we can use to apply the transformations
27    let mut buffer = {
28        let mut buffer = (*item.shape_cd).clone();
29        buffer.surrogate = None; //remove the surrogate for faster transforms, we don't need it for the buffer shape
30        buffer
31    };
32
33    let mut best: Option<(DTransformation, LBFLoss)> = None;
34
35    //calculate the number of uniform and local search samples
36    let ls_sample_budget = (config.n_samples as f32 * config.ls_frac) as usize;
37    let uni_sample_budget = config.n_samples - ls_sample_budget;
38
39    let mut bin_sampler = UniformRectSampler::new(cde.bbox(), item);
40
41    for i in 0..uni_sample_budget {
42        let d_transf = bin_sampler.sample(rng);
43        let transf = d_transf.compose();
44        if !cde.surrogate_collides(surrogate, &transf, filter) {
45            //if no collision is detected on the surrogate, apply the transformation
46            buffer.transform_from(&item.shape_cd, &transf);
47            let cost = LBFLoss::from_shape(&buffer);
48
49            //only validate the sample if it possibly can replace the current best
50            let worth_testing = match (best.as_ref(), &cost) {
51                (Some((_, best_cost)), cost) => {
52                    cost.partial_cmp(best_cost).unwrap() == Ordering::Less
53                }
54                (None, _) => true,
55            };
56
57            if worth_testing && !cde.poly_collides(&buffer, filter) {
58                //sample is valid and improves on the current best
59                debug!("[UNI: {i}/{uni_sample_budget}] better: {} ", &d_transf);
60
61                best = Some((d_transf, cost));
62
63                let tightened_sampling_bbox = cost.tighten_sample_bbox(bin_sampler.bbox);
64                bin_sampler = UniformRectSampler::new(tightened_sampling_bbox, item);
65            }
66        }
67    }
68
69    *sample_counter += uni_sample_budget;
70
71    //if a valid sample was found during the uniform sampling, perform local search around it
72    let (best_sample, best_cost) = best.as_mut()?;
73
74    /*
75    The local search samples in a normal distribution.
76    Throughout the course of the local search, the mean of the distribution is updated to the best found sample.
77    And the standard deviation tightens, to focus the search around the best sample.
78     */
79
80    let mut ls_sampler = LSSampler::from_defaults(item, *best_sample, cde.bbox());
81
82    for i in 0..ls_sample_budget {
83        let d_transf = ls_sampler.sample(rng);
84        let transf = d_transf.compose();
85        if !cde.surrogate_collides(surrogate, &transf, filter) {
86            buffer.transform_from(&item.shape_cd, &transf);
87            let cost = LBFLoss::from_shape(&buffer);
88
89            //only validate the sample if it possibly can replace the current best
90            let worth_testing = cost < *best_cost;
91
92            if worth_testing && !cde.poly_collides(&buffer, filter) {
93                //sample is valid and improves on the current best
94                ls_sampler.shift_mean(d_transf);
95                debug!("[LS: {i}/{ls_sample_budget}] better: {}", &d_transf);
96                (*best_sample, *best_cost) = (d_transf, cost);
97            }
98        }
99        let progress_pct = i as f32 / ls_sample_budget as f32;
100        ls_sampler.decay_stddev(progress_pct);
101    }
102
103    *sample_counter += ls_sampler.n_samples;
104
105    best
106}
107
108pub fn item_placement_order(instance: &impl Instance) -> Vec<usize> {
109    //sort the items by descending diameter
110    instance
111        .items()
112        .sorted_by_key(|item| Reverse(OrderedFloat(item.shape_cd.diameter)))
113        .map(|item| item.id)
114        .collect_vec()
115}
lbf/opt/search.rs

lbf/opt/
search.rs
