قبل مائة عام ، طرح عالم الرياضيات العظيم ديفيد هيلبرت سؤالًا بحثيًا من مجال الرياضيات البحتة. التطورات الأخيرة في نظرية التحسين تجلب عمل هيلبرت إلى عالم الروبوتات
قبل وقت طويل من تشغيل الروبوتات ، ويمكن أن تقود السيارات نفسها ، اعتبر علماء الرياضيات سؤالًا رياضيًا بسيطًا. أخيرًا ، قاموا بفرزها ووضعها جانبًا - دون أن يكونوا قادرين على معرفة أن جسم فضولهم الرياضي سيظهر في آلات المستقبل البعيد.
لقد حان المستقبل. نتيجة
للعمل الجديد الذي قام به أمير علي أحمدي وأنيرودا ماجومارا من جامعة برينستون ، أصبحت المشكلة الكلاسيكية في الرياضيات البحتة جاهزة لتقديم دليل حديدي على أن الطائرات الآلية والطائرات الآلية لن تصطدم بالأشجار أو سيارات الأجرة في الممر القادم.
قالت
جورجينا هول ، طالبة دراسات عليا من جامعة برينستون تعاونت مع أحمدي في هذا العمل: "هناك ضمان كامل 100٪ يمكن إثباته بأن نظامك" يمكنه تجنب الاصطدامات.
أمير علي أحمدي ، أستاذ من جامعة برينستونيتم أخذ الضمان في مكان غير متوقع - في مشكلة رياضية تعرف باسم "
مجموع المربعات ". تم وضعها في عام 1900 من قبل عالم الرياضيات العظيم ديفيد هيلبرت. وتساءل عما إذا كان يمكن دائمًا التعبير عن معادلات معينة على أنها مجموع مصطلحين منفصلين ، كل منهما مربع.
أجاب علماء الرياضيات على سؤال هيلبرت بعد بضعة عقود. بعد ذلك ، وبعد 90 عامًا تقريبًا ، اكتشف علماء الكمبيوتر والمهندسون أن هذه الخاصية الحسابية - قابلية المعادلة من حيث مجموع المربعات - تساعد في حل العديد من المشكلات الحقيقية التي يرغبون في حلها.
قال أحمدي: "يتم استخدام الكثير من الرياضيات الكلاسيكية في القرن التاسع عشر في ما أقوم به ، إلى جانب الرياضيات الحسابية الحديثة جدًا".
ومع ذلك ، بمجرد أن أدرك الباحثون أن مجموع المربعات يمكن أن يساعد في الإجابة على أنواع كثيرة من الأسئلة ، واجهوا مشاكل في تطبيق هذا النهج. يقضي العمل الجديد على واحدة من أكبر هذه المشكلات ، مما يجبر السؤال الرياضي القديم على حل بعض أهم القضايا التكنولوجية في عصرنا.
مضمون إيجابي
ماذا يعني أن كمية معينة هي مجموع المربعات؟ خذ الرقم 13. هذا هو مجموع مربعين - 2
2 و 3
2 . الرقم 34 هو مجموع 3
2 و 5
2 .
بدلاً من الأرقام ، يتعامل سؤال هيلبرت -
المشكلات الـ 17 من بين 23
مشكلة التي اقترحها في فجر القرن العشرين - مع كثيرات الحدود مثل 5x
2 + 16x + 13. ويمكن أيضًا تمثيل كثيرات الحدود في بعض الأحيان كمبالغ من المربعات. على سبيل المثال ، يمكن إعادة كتابة 5x
2 + 16x + 13 بالشكل (x + 2)
2 + (2x + 3)
2 .
عندما يكون التعبير هو مجموع المربعات ، فأنت تعلم أنه دائمًا موجب (جميع الأرقام [الحقيقية] مربعة تعطي رقمًا موجبًا أو صفرًا ، ومجموع الأرقام الموجبة موجبًا). أراد هيلبرت أن يعرف ما إذا كان هذا يعمل بطريقة أخرى: هل يمكن التعبير عن جميع كثيرات الحدود غير السلبية كمجموع مربعات الدوال العقلانية. في عام 1927 ، أثبت عالم الرياضيات إميل آرتين أن فرضية هيلبرت كانت صحيحة.
هذه العلاقة مفيدة للغاية. إذا تم إعطاؤك كثيرات الحدود المعقدة ، مع رفع العشرات من المتغيرات إلى أعلى درجة ، فمن الصعب جدًا تحديد ما إذا كانت دائمًا غير سلبية. "بعض كثيرات الحدود من الواضح أنها ليست سلبية ، والبعض الآخر ليس كذلك. قال أحمدي: "من الصعب اختبارهم لعدم السلبية".
ولكن بمجرد أن تظهر أنه يمكن التعبير عن هذا كثير الحدود من حيث مجموع المربعات ، فإن عدم السلبية سيكون ببساطة نتيجة لذلك. قال
بابلو باريلو ، عالم الكمبيوتر والمهندس في معهد ماساتشوستس للتكنولوجيا ، الذي شارك في سحب مسألة مجموع المربعات في عالم التطبيقات: "مجموع المربعات يمنحك شهادة إيجابية إيجابية".
إن معرفة أن كثيرات حدود معينة دائمًا ما تكون غير سلبية قد تبدو مثل التفاهة الرياضية. ولكن بعد مائة عام من طرح هيلبرت سؤاله ، تبين أن عدم السلبية من كثيرات الحدود هو الحل للمشاكل التطبيقية التي تؤثر علينا جميعًا.
أفضل طريقة
يلتقي مجموع المربعات مع العالم الحقيقي في مجال التحسين. تنشغل
نظرية التحسين بإيجاد أفضل طريقة للقيام بشيء ما أثناء وجودك ضمن القيود - على سبيل المثال ، العثور على أفضل طريق للوصول إلى العمل ، نظرًا لحالة الطريق والتوقف الضروري الذي تحتاج إليه على طول الطريق. غالبًا ما يمكن اختزال مثل هذه السيناريوهات إلى كثيرات الحدود. في مثل هذه الحالات ، من الممكن حل أو "تحسين" السيناريو من خلال إيجاد القيمة الدنيا التي يأخذها كثير الحدود.
إيجاد الحد الأدنى من كثير الحدود مع العديد من المتغيرات مهمة صعبة. لا توجد خوارزمية بسيطة من الكتاب المدرسي لحساب الحد الأدنى لقيمة كثيرات الحدود المعقدة ؛ علاوة على ذلك ، يصعب تكوينها على رسم بياني.
قاعة جورجينابما أن الحد الأدنى لقيمة كثير الحدود يصعب حسابه مباشرة ، يقوم الباحثون بافتراضات حول هذه القيمة بطرق أخرى. هنا يأتي دور عدم السلبية ، ومسألة ما إذا كان كثير الحدود هو مجموع المربعات. قالت ريها توماس ، عالمة الرياضيات في جامعة واشنطن: "ضمان عدم السلبية هو جوهر جميع قضايا التحسين".
إحدى الطرق للعثور على الحد الأدنى للقيمة هي طرح السؤال: ما هي القيمة القصوى التي يمكن طرحها من كثيرات الحدود غير السلبية بحيث لا تصبح سلبية في مرحلة ما؟ للإجابة على السؤال ، من الضروري التحقق من القيم المختلفة - هل من الممكن طرح 3 بحيث لا تصبح سلبية؟ و 4؟ و 5؟ كرر الإجراء ، في كل خطوة تحتاج إلى معرفة ما إذا كان كثير الحدود يبقى غير سلبي. يتم التحقق من ذلك من خلال إمكانية التعبير عنه كمجموع المربعات.
قال أحمدي: "السؤال الذي يجب طرحه هو" هل كثير الحدود غير سلبي؟ "المشكلة هي أنه مع وجود عدد كبير من المتغيرات ، يصعب الإجابة على هذا السؤال. "لذلك ، نستخدم مجموع المربعات كبديل عن السلبية."
بمجرد أن يصبح الباحثون على دراية بالحد الأدنى - القيمة المثلى من كثيرات الحدود - يمكنهم استخدام طرق أخرى لتحديد معلمات الإدخال التي تؤدي إلى هذه القيمة. ومع ذلك ، من أجل عدم السلبية للمساعدة في حل مشاكل التحسين ، تحتاج إلى التوصل إلى طريقة لحساب ما إذا كان يتم التعبير عن كثيرات الحدود من حيث مجموع المربعات. ولكي يتمكن الباحثون من القيام بذلك ، استغرق الأمر 100 عامًا من لحظة طرح هيلبرت السؤال.
كسر المشكلة
انتقلت مشكلة هيلبرت السابعة عشرة من عالم الرياضيات البحتة إلى المستوى التطبيقي حوالي عام 2000. في ذلك الوقت ، توصل العديد من الباحثين إلى خوارزمية للتحقق مما إذا كان يمكن تمثيل كثير الحدود من حيث مجموع المربعات. لقد وصلوا إلى هذه النقطة عن طريق حل المشكلة المربعة من خلال "
برمجة شبه محددة " ، بفضلها أجهزة الكمبيوتر قادرة على التعامل مع مثل هذه المهمة. وقد أتاح ذلك للباحثين من مجالات مثل علوم الكمبيوتر والهندسة استخدام إمكانات عدم السلبية لتوجيه عمليات البحث نحو الطرق المثلى لحل المشكلات.
أنيرودا ماجومدارلكن البرمجة شبه المحددة لها قيود كبيرة: فهي تعمل ببطء على المهام الكبيرة وغير قادرة على معالجة بعض أكثر الحدود تعقيدًا التي يهتم بها الباحثون بشكل خاص. يمكن استخدام البرمجة شبه المحددة للتحلل في مجموع المربعات مثل كثيرات الحدود التي تتكون من ما لا يزيد عن اثنتي عشرة متغيرات مرفوعة إلى قوة لا تزيد عن 6. كثيرات الحدود التي تصف المشاكل الهندسية المعقدة - على سبيل المثال ، ضمان بقاء الروبوت على قدميه - يمكن أدخل 50 متغيرًا ، أو حتى أكثر من ذلك. يمكن للبرنامج مضغ مثل كثير الحدود حتى نهاية الوقت ، ولا يزال لا يعطي مجموع المربعات.
في
ورقة نشرت على الإنترنت في يونيو الماضي ، يشرح أحمدي وماجومدار كيفية الالتفاف حول العمل البطيء للبرمجة شبه المحددة. بدلاً من محاولة العثور على التحلل في مجموع المربعات باستخدام برنامج واحد بطيء ، يظهرون كيف يمكنك القيام بذلك باستخدام حل
تسلسل المهام الأبسط ، والتي ستكون أسرع بكثير في الحساب.
تسمى المهام من هذا النوع "الخطي" ، وقد تم تطويرها في أربعينيات القرن العشرين لحل مشكلات التحسين المتعلقة بالقضايا العسكرية. أصبحت البرامج الخطية مفهومة جيدًا وحلها بسرعة. في ورقة جديدة ، يظهر أحمدي وماجومدار أنه من الممكن حل العديد من البرامج الخطية المتصلة (أو ، في بعض الحالات ، نوع مختلف من المشاكل ، برنامج مخروطي من الدرجة الثانية) ، ودمج النتائج للحصول على شيء جيد تقريبًا مثل الإجابة ، والتي يمكن أن تعطي برنامجًا لبرمجة شبه محددة. ونتيجة لذلك ، يمتلك المهندسون أداة جديدة وعملية يمكنهم استخدامها للتحقق من عدم السلبية وإيجاد التحلل بسرعة في مجموع المربعات.
قال ماجومدار: "لقد درسنا العديد من مشكلات الروبوتات ونظرية التحكم ، وأظهرنا أن جودة الحلول الناتجة مفيدة للاستخدام العملي ، وأن حسابها أسرع بكثير".
دليل السلامة
سرعة القرار هي كل شيء إذا كنت في سيارة روبوتية. في مثل هذه الحالة ، يمكن أن يكون كثير الحدود بمثابة حاجز رياضي تم إعداده حول العوائق التي لا تريد أن تصطدم بها - إذا كان من الممكن حسابها بسرعة كافية.
تخيل مثالاً بسيطًا: سيارة روبوتية في موقف سيارات عملاق. لا يوجد شيء في ساحة الانتظار باستثناء كشك الأمن في النهاية البعيدة. مهمتك هي برمجة الآلة بحيث لا تصطدم أبداً بهذا الكشك.
في هذه الحالة ، يمكنك سحب الشبكة إلى موقف السيارات. ثم قم بعمل كثيرات الحدود التي تأخذ النقاط على الشبكة كمدخل. تأكد من أن قيم كثيرات الحدود في موقع الآلة سلبية ، وأن القيمة في موقع كشك الحارس إيجابية.
في مجموعة من النقاط بين سيارتك والمقصورة ، ستنتقل كثيرات الحدود من ناقص إلى زائد. نظرًا لأنه يمكن تحديد مكان سيارتك فقط حيث يكون كثير الحدود سالبًا ، فإن هذه النقاط ستلعب دور الجدار.
"إذا بدأت من مكان معين ، فلن يعبر الروبوت الخط الذي تقف وراءه العقبة. قال أحمدي: "يمنحك هذا دليلاً رسميًا على تجنب الاصطدامات".
بالطبع ، سيكون من غير المناسب إذا كان هذا الجدار في منتصف المسار بين الماكينة والمقصورة. من الضروري بناء كثيرات الحدود بحيث يحيط الجدار بالعقبة بإحكام قدر الإمكان. هذا الخيار سيحمي المقصورة ويعطي السيارة مساحة كبيرة للحركة.
من الناحية العملية ، من الضروري تقليل القيمة - المسافة بين الجدار والمربع - لذلك تحتاج إلى تغيير الرسم البياني الخاص متعدد الحدود ومعرفة المدى الذي يمكن نقله حتى ينتقل من ناقص إلى زائد. يتم تحقيق ذلك عن طريق التحقق مما إذا كان كثير الحدود يبقى مجموع المربعات.
مواقف السيارات الفارغة تقريبا شيء واحد. ولكن في سيناريوهات واقعية للتحكم في الماكينة ، تكتشف مستشعراتها باستمرار عوائق متحركة جديدة - السيارات والدراجات والأطفال. في كل مرة تظهر عقبة جديدة أو تتحرك عقبة معروفة ، تحتاج الآلة إلى بناء كثيرات الحدود المعقدة الجديدة التي تحيط بهذه العقبات. هذا هو الكثير من الشيكات على مقدار المربعات التي يجب إجراؤها على الطاير.
قبل سبع سنوات ، تخيل زوج آخر من الباحثين بالفعل أنه يمكن استخدام مثل هذه التقنيات للعمل مع كثيرات الحدود لفصل الهواتف الآلية وتلك الأماكن التي لا يجب أن تقع فيها. ولكن في ذلك الوقت ، جعلت قوة أجهزة الكمبيوتر هذه الفكرة حلما.
يفتح النهج الجديد لأحمدي وماجومدار طريقة جديدة لإجراء مثل هذه الحوسبة الفورية. لذا ، إذا ومتى تمكنت أجهزة الروبوت من التحرك بأمان في جميع أنحاء العالم ، فيمكننا شكر Google و Tesla - وكذلك Hilbert على ذلك.