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

lbf/opt/
search.rs
