新的計算方法輔助堅固容器內物體的密集擺放
引言
密集地擺放物體是一個古老而困難的問題，直到現在仍然沒有確保的解決方法。然而一個由麻省理工學院 (MIT) 和麻省麥克斯威爾創業公司 (Inkbit) 的研究團隊最近推出的新的計算方法——"密集、無縫鎖定且可擴充套件的光譜擺放" (SSP)——為此問題帶來了一些重要的突破。這項技術的應用，可以幫助倉儲和運輸公司更有效地將物體擺放在不同大小的箱子中；同時在三維列印領域也有很大的應用潛力。
困難的問題
在 1611 年，著名的天文學家約翰內斯·開普勒提出了一個關於如何以最密集的方式擺放相等大小的球體的問題。開普勒得出的最佳方式被稱為"面心立方晶格"，通常用於雜貨店展示橙子。然而關於如何最優地擺放不同大小和形狀的 3D 物體的更一般的問題，仍然沒有解決方案。
這個問題被歸類為 NP-hard 問題，這意味著只要求得一個近似解即可，即使是非常精確的近似解，也需要耗費極長的計算時間，可能需要數年甚至數十年，具體取決於需要擺放的物體數量及其形狀大小。然而最近的一項研究利用了一種新的計算方法，使得這個本來複雜的任務更易處理。
新的計算方法
這項名為"密集、無縫鎖定且可擴充套件的光譜擺放" (SSP)的技術是由一個由 MIT 和 Inkbit 的研究團隊開發的。它將容器內的擺放位置問題轉化為計算問題，以實現更高效的解決方案。
SSP 算法的第一步是確保一個固定容器內的 3D 物體的排列線序。一種可能的方法是從最大的物體開始，最後放置最小的物體。接下來，將每個物體放入容器。為了方便這個過程，容器被分割成一個個小的立方體單元，每個立方體單元可能只有一立方毫米大小。立方體網格顯示了容器的哪些部分已經填滿，哪些部分是空的。待擺放的物體也被切割成一個個與容器中的立方體單元相同大小的小立方體。然後，該算法在每個立方體單元上計算一個稱為碰撞指標的數量，以確保物體的可用空間。碰撞指標是透過將物體的中心放置在容器的每個立方體單元上，然後計算物體與立方體單元的重疊程度來計算的。只有在重疊程度為零的位置，也就是沒有碰撞的位置，物體才能被放置。
下一步是從所有可能的位置中篩選出最佳的位置來放置物體。為了完成這個任務，研究人員在每個立方體單元上計算另一個指標，這個指標設計用於最大程度地增加物體擺放密度。該指標衡量的是物體與容器之間的間隙或者移動中的物體與容器內已經放置的物體之間的間隙。例如，如果物體放在中間位置，該指標可能會給出一個較高的值。然而目標是最小化物體之間的間隙，這可以透過將物體放在指標值最低的位置實現。Matusik 教授解釋說："這有點像俄羅斯方塊遊戲，你希望留下的空間盡可能少。"
然而前述討論只涉及物體在空間中的固定方向的移動。對於相同物體的不同方向，計算機可能需要嘗試多種可能的擺放位置，直到找到最符合要求的方向。SSP 算法的最後一步是確保對於一個可行的擺放方案，每個物體都能夠在分配的位置進入容器，或者等效地說，每個物體在容器被開啟時都能夠與其他物體分離。
新方法的優勢與應用
該團隊使用了一種數學技術，即快速傅立葉變換 (FFT)，這種技術在擺放問題上從未應用過。透過使用 FFT，可以透過幾個簡單的乘法等有限的計算方式解決容器內所有立方體單元中最小化重疊和間隙的問題，而不是測試所有可能的位置。這使得擺放速度提高了數個數量級。
在一次展示中，新算法在 40 秒內有效地擺放了 670 個物體，達到了約 36%的擺放密度。而在兩個小時內，光譜擺放算法安排了 6,596 個物體，其擺放密度達到了 37.30%。瑪圖西克教授表示："我們得到的密度接近 40%，遠遠優於傳統算法，而且速度也更快。"
這項研究代表著"有效組織 3D 物體一直存在的問題的突破性解決方案"，普渡大學電腦科學教授貝德裏赫·貝內斯評論說："該解決方案最大化了擺放密度，並且在許多實際應用領域具有潛在價值，從機器人技術到制造業。此外無鎖定的解決方案非常適合計算機控制的環境。"
這項技術當然可以用於倉儲和運輸公司，這些公司需要將各種物體定期放入不同大小的箱子中。然而瑪圖西克教授和他的同事們對三維列印領域的應用特別感興趣。通常情況下，3D 列印的零件是批次生產的，並放置在託盤上。然而當前的方法對容器的利用率非常有限，通常只在 20%左右。瑪圖西克教授補充說："如果我們能夠增加擺放密度，就能夠提高列印過程的整體效率，從而降低零件的整體成本。"
結論與展望
雖然這項研究為三維列印和堅固物體的擺放提供了新的改進方法，但如何最佳地擺放可變形物體或由多個存取在一起的剛體部分組成的物體的問題仍然是一個未解決的問題，可能在未來的研究中得到解決。然而如果人們發現自己需要在短時間內將超過 6,000 個物體放入一個儲存箱中，並不需要感到絕望，因為只需要一個算法就可以解決這個困難。
總之這項新的計算方法為解決物體密集擺放的問題提供了一個突破性的解決方案。該方法不僅在效率上超越了傳統的算法，而且在多個應用領域中具有潛力，從倉儲和運輸到三維列印。隨著這一領域的不斷發展，人們可以期待更多的創新和改進，從而使物體擺放更加高效和可靠。
