Learning Constraints from Locally-Optimal Demonstrations under Cost Function Uncertainty Article Swipe

PDF

Glen Chou , Necmiye Özay , Dmitry Berenson ·

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2001.09336

We present an algorithm for learning parametric constraints from locally-optimal demonstrations, where the cost function being optimized is uncertain to the learner. Our method uses the Karush-Kuhn-Tucker (KKT) optimality conditions of the demonstrations within a mixed integer linear program (MILP) to learn constraints which are consistent with the local optimality of the demonstrations, by either using a known constraint parameterization or by incrementally growing a parameterization that is consistent with the demonstrations. We provide theoretical guarantees on the conservativeness of the recovered safe/unsafe sets and analyze the limits of constraint learnability when using locally-optimal demonstrations. We evaluate our method on high-dimensional constraints and systems by learning constraints for 7-DOF arm and quadrotor examples, show that it outperforms competing constraint-learning approaches, and can be effectively used to plan new constraint-satisfying trajectories in the environment.

Related Topics

Computer Science

Mathematics

Artificial Intelligence

Concepts

Karush–Kuhn–Tucker conditions Mathematical optimization Constraint (computer-aided design) Learnability Function (biology) Computer science Integer (computer science) Constraint learning Parametric statistics Mathematics Constraint programming Artificial intelligence Constraint logic programming Stochastic programming Biology Programming language Statistics Geometry Evolutionary biology

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2001.09336
PDF: https://arxiv.org/pdf/2001.09336
OA Status: green
Cited By: 2
References: 23
Related Works: 10
OpenAlex ID: https://openalex.org/W3001217416

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W3001217416

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2001.09336

Digital Object Identifier
Title: Learning Constraints from Locally-Optimal Demonstrations under Cost Function Uncertainty

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2020

Year of publication
Publication date: 2020-01-25

Full publication date if available
Authors: Glen Chou, Necmiye Özay, Dmitry Berenson

List of authors in order
Landing page: https://arxiv.org/abs/2001.09336

Publisher landing page
PDF URL: https://arxiv.org/pdf/2001.09336

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2001.09336

Direct OA link when available
Concepts: Karush–Kuhn–Tucker conditions, Mathematical optimization, Constraint (computer-aided design), Learnability, Function (biology), Computer science, Integer (computer science), Constraint learning, Parametric statistics, Mathematics, Constraint programming, Artificial intelligence, Constraint logic programming, Stochastic programming, Biology, Programming language, Statistics, Geometry, Evolutionary biology

Top concepts (fields/topics) attached by OpenAlex
Cited by: 2

Total citation count in OpenAlex
Citations by year (recent): 2025: 1, 2020: 1

Per-year citation counts (last 5 years)
References (count): 23

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W3001217416
doi	https://doi.org/10.48550/arxiv.2001.09336
ids.doi	https://doi.org/10.48550/arxiv.2001.09336
ids.mag	3001217416
ids.openalex	https://openalex.org/W3001217416
fwci
type	preprint
title	Learning Constraints from Locally-Optimal Demonstrations under Cost Function Uncertainty
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T12072
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9951000213623047
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Machine Learning and Algorithms
topics[1].id	https://openalex.org/T10906
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9945999979972839
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1702
topics[1].subfield.display_name	Artificial Intelligence
topics[1].display_name	AI-based Problem Solving and Planning
topics[2].id	https://openalex.org/T10653
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.9739999771118164
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2207
topics[2].subfield.display_name	Control and Systems Engineering
topics[2].display_name	Robot Manipulation and Learning
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C50454189
concepts[0].level	2
concepts[0].score	0.7970420122146606
concepts[0].wikidata	https://www.wikidata.org/wiki/Q2075125
concepts[0].display_name	Karush–Kuhn–Tucker conditions
concepts[1].id	https://openalex.org/C126255220
concepts[1].level	1
concepts[1].score	0.746315062046051
concepts[1].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[1].display_name	Mathematical optimization
concepts[2].id	https://openalex.org/C2776036281
concepts[2].level	2
concepts[2].score	0.7056311368942261
concepts[2].wikidata	https://www.wikidata.org/wiki/Q48769818
concepts[2].display_name	Constraint (computer-aided design)
concepts[3].id	https://openalex.org/C2777723229
concepts[3].level	2
concepts[3].score	0.6958795785903931
concepts[3].wikidata	https://www.wikidata.org/wiki/Q4367921
concepts[3].display_name	Learnability
concepts[4].id	https://openalex.org/C14036430
concepts[4].level	2
concepts[4].score	0.5659079551696777
concepts[4].wikidata	https://www.wikidata.org/wiki/Q3736076
concepts[4].display_name	Function (biology)
concepts[5].id	https://openalex.org/C41008148
concepts[5].level	0
concepts[5].score	0.5516173839569092
concepts[5].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[5].display_name	Computer science
concepts[6].id	https://openalex.org/C97137487
concepts[6].level	2
concepts[6].score	0.4800775647163391
concepts[6].wikidata	https://www.wikidata.org/wiki/Q729138
concepts[6].display_name	Integer (computer science)
concepts[7].id	https://openalex.org/C29230964
concepts[7].level	5
concepts[7].score	0.476521372795105
concepts[7].wikidata	https://www.wikidata.org/wiki/Q5164376
concepts[7].display_name	Constraint learning
concepts[8].id	https://openalex.org/C117251300
concepts[8].level	2
concepts[8].score	0.4510747790336609
concepts[8].wikidata	https://www.wikidata.org/wiki/Q1849855
concepts[8].display_name	Parametric statistics
concepts[9].id	https://openalex.org/C33923547
concepts[9].level	0
concepts[9].score	0.31014156341552734
concepts[9].wikidata	https://www.wikidata.org/wiki/Q395
concepts[9].display_name	Mathematics
concepts[10].id	https://openalex.org/C173404611
concepts[10].level	3
concepts[10].score	0.2837389409542084
concepts[10].wikidata	https://www.wikidata.org/wiki/Q528588
concepts[10].display_name	Constraint programming
concepts[11].id	https://openalex.org/C154945302
concepts[11].level	1
concepts[11].score	0.2257971465587616
concepts[11].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[11].display_name	Artificial intelligence
concepts[12].id	https://openalex.org/C176783269
concepts[12].level	4
concepts[12].score	0.17115017771720886
concepts[12].wikidata	https://www.wikidata.org/wiki/Q5164378
concepts[12].display_name	Constraint logic programming
concepts[13].id	https://openalex.org/C137631369
concepts[13].level	2
concepts[13].score	0.05449596047401428
concepts[13].wikidata	https://www.wikidata.org/wiki/Q7617831
concepts[13].display_name	Stochastic programming
concepts[14].id	https://openalex.org/C86803240
concepts[14].level	0
concepts[14].score	0.0
concepts[14].wikidata	https://www.wikidata.org/wiki/Q420
concepts[14].display_name	Biology
concepts[15].id	https://openalex.org/C199360897
concepts[15].level	1
concepts[15].score	0.0
concepts[15].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[15].display_name	Programming language
concepts[16].id	https://openalex.org/C105795698
concepts[16].level	1
concepts[16].score	0.0
concepts[16].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[16].display_name	Statistics
concepts[17].id	https://openalex.org/C2524010
concepts[17].level	1
concepts[17].score	0.0
concepts[17].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[17].display_name	Geometry
concepts[18].id	https://openalex.org/C78458016
concepts[18].level	1
concepts[18].score	0.0
concepts[18].wikidata	https://www.wikidata.org/wiki/Q840400
concepts[18].display_name	Evolutionary biology
keywords[0].id	https://openalex.org/keywords/karush–kuhn–tucker-conditions
keywords[0].score	0.7970420122146606
keywords[0].display_name	Karush–Kuhn–Tucker conditions
keywords[1].id	https://openalex.org/keywords/mathematical-optimization
keywords[1].score	0.746315062046051
keywords[1].display_name	Mathematical optimization
keywords[2].id	https://openalex.org/keywords/constraint
keywords[2].score	0.7056311368942261
keywords[2].display_name	Constraint (computer-aided design)
keywords[3].id	https://openalex.org/keywords/learnability
keywords[3].score	0.6958795785903931
keywords[3].display_name	Learnability
keywords[4].id	https://openalex.org/keywords/function
keywords[4].score	0.5659079551696777
keywords[4].display_name	Function (biology)
keywords[5].id	https://openalex.org/keywords/computer-science
keywords[5].score	0.5516173839569092
keywords[5].display_name	Computer science
keywords[6].id	https://openalex.org/keywords/integer
keywords[6].score	0.4800775647163391
keywords[6].display_name	Integer (computer science)
keywords[7].id	https://openalex.org/keywords/constraint-learning
keywords[7].score	0.476521372795105
keywords[7].display_name	Constraint learning
keywords[8].id	https://openalex.org/keywords/parametric-statistics
keywords[8].score	0.4510747790336609
keywords[8].display_name	Parametric statistics
keywords[9].id	https://openalex.org/keywords/mathematics
keywords[9].score	0.31014156341552734
keywords[9].display_name	Mathematics
keywords[10].id	https://openalex.org/keywords/constraint-programming
keywords[10].score	0.2837389409542084
keywords[10].display_name	Constraint programming
keywords[11].id	https://openalex.org/keywords/artificial-intelligence
keywords[11].score	0.2257971465587616
keywords[11].display_name	Artificial intelligence
keywords[12].id	https://openalex.org/keywords/constraint-logic-programming
keywords[12].score	0.17115017771720886
keywords[12].display_name	Constraint logic programming
keywords[13].id	https://openalex.org/keywords/stochastic-programming
keywords[13].score	0.05449596047401428
keywords[13].display_name	Stochastic programming
language	en
locations[0].id	pmh:oai:arXiv.org:2001.09336
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2001.09336
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2001.09336
locations[1].id	doi:10.48550/arxiv.2001.09336
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2001.09336
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5006149535
authorships[0].author.orcid	https://orcid.org/0000-0003-4444-3631
authorships[0].author.display_name	Glen Chou
authorships[0].author_position	first
authorships[0].raw_author_name	Glen Chou
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5054418471
authorships[1].author.orcid	https://orcid.org/0000-0002-5552-4392
authorships[1].author.display_name	Necmiye Özay
authorships[1].author_position	middle
authorships[1].raw_author_name	Necmiye Ozay
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5083082888
authorships[2].author.orcid	https://orcid.org/0000-0002-9712-109X
authorships[2].author.display_name	Dmitry Berenson
authorships[2].author_position	last
authorships[2].raw_author_name	Dmitry Berenson
authorships[2].is_corresponding	False
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2001.09336
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2020-01-30T00:00:00
display_name	Learning Constraints from Locally-Optimal Demonstrations under Cost Function Uncertainty
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T12072
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9951000213623047
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Machine Learning and Algorithms
related_works	https://openalex.org/W4385764505, https://openalex.org/W3003470753, https://openalex.org/W2381224930, https://openalex.org/W2121633746, https://openalex.org/W2729734553, https://openalex.org/W2611943309, https://openalex.org/W2022053804, https://openalex.org/W2044707813, https://openalex.org/W2042246031, https://openalex.org/W2296605212
cited_by_count	2
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2020
counts_by_year[1].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2001.09336
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2001.09336
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2001.09336
primary_location.id	pmh:oai:arXiv.org:2001.09336
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2001.09336
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2001.09336
publication_date	2020-01-25
publication_year	2020
referenced_works	https://openalex.org/W2842089854, https://openalex.org/W2736457169, https://openalex.org/W2158607953, https://openalex.org/W2107308405, https://openalex.org/W3032881759, https://openalex.org/W2296319761, https://openalex.org/W2515082088, https://openalex.org/W1999874108, https://openalex.org/W2738190501, https://openalex.org/W2998710335, https://openalex.org/W2116341587, https://openalex.org/W1986014385, https://openalex.org/W2169498096, https://openalex.org/W2597829367, https://openalex.org/W2737702598, https://openalex.org/W2027161089, https://openalex.org/W2019965290, https://openalex.org/W2061562262, https://openalex.org/W3023096123, https://openalex.org/W2103254706, https://openalex.org/W2963762522, https://openalex.org/W2571352963, https://openalex.org/W2137254586
referenced_works_count	23
abstract_inverted_index.a	34, 56, 64
abstract_inverted_index.We	0, 72, 95
abstract_inverted_index.an	2
abstract_inverted_index.be	122
abstract_inverted_index.by	53, 61, 104
abstract_inverted_index.in	130
abstract_inverted_index.is	17, 67
abstract_inverted_index.it	115
abstract_inverted_index.of	30, 50, 79, 88
abstract_inverted_index.on	76, 99
abstract_inverted_index.or	60
abstract_inverted_index.to	19, 40, 125
abstract_inverted_index.Our	22
abstract_inverted_index.and	84, 102, 110, 120
abstract_inverted_index.are	44
abstract_inverted_index.arm	109
abstract_inverted_index.can	121
abstract_inverted_index.for	4, 107
abstract_inverted_index.new	127
abstract_inverted_index.our	97
abstract_inverted_index.the	12, 20, 25, 31, 47, 51, 70, 77, 80, 86, 131
abstract_inverted_index.cost	13
abstract_inverted_index.from	8
abstract_inverted_index.plan	126
abstract_inverted_index.sets	83
abstract_inverted_index.show	113
abstract_inverted_index.that	66, 114
abstract_inverted_index.used	124
abstract_inverted_index.uses	24
abstract_inverted_index.when	91
abstract_inverted_index.with	46, 69
abstract_inverted_index.(KKT)	27
abstract_inverted_index.7-DOF	108
abstract_inverted_index.being	15
abstract_inverted_index.known	57
abstract_inverted_index.learn	41
abstract_inverted_index.local	48
abstract_inverted_index.mixed	35
abstract_inverted_index.using	55, 92
abstract_inverted_index.where	11
abstract_inverted_index.which	43
abstract_inverted_index.(MILP)	39
abstract_inverted_index.either	54
abstract_inverted_index.limits	87
abstract_inverted_index.linear	37
abstract_inverted_index.method	23, 98
abstract_inverted_index.within	33
abstract_inverted_index.analyze	85
abstract_inverted_index.growing	63
abstract_inverted_index.integer	36
abstract_inverted_index.present	1
abstract_inverted_index.program	38
abstract_inverted_index.provide	73
abstract_inverted_index.systems	103
abstract_inverted_index.evaluate	96
abstract_inverted_index.function	14
abstract_inverted_index.learner.	21
abstract_inverted_index.learning	5, 105
abstract_inverted_index.algorithm	3
abstract_inverted_index.competing	117
abstract_inverted_index.examples,	112
abstract_inverted_index.optimized	16
abstract_inverted_index.quadrotor	111
abstract_inverted_index.recovered	81
abstract_inverted_index.uncertain	18
abstract_inverted_index.conditions	29
abstract_inverted_index.consistent	45, 68
abstract_inverted_index.constraint	58, 89
abstract_inverted_index.guarantees	75
abstract_inverted_index.optimality	28, 49
abstract_inverted_index.parametric	6
abstract_inverted_index.approaches,	119
abstract_inverted_index.constraints	7, 42, 101, 106
abstract_inverted_index.effectively	123
abstract_inverted_index.outperforms	116
abstract_inverted_index.safe/unsafe	82
abstract_inverted_index.theoretical	74
abstract_inverted_index.environment.	132
abstract_inverted_index.learnability	90
abstract_inverted_index.trajectories	129
abstract_inverted_index.incrementally	62
abstract_inverted_index.demonstrations	32
abstract_inverted_index.demonstrations,	10, 52
abstract_inverted_index.demonstrations.	71, 94
abstract_inverted_index.locally-optimal	9, 93
abstract_inverted_index.conservativeness	78
abstract_inverted_index.high-dimensional	100
abstract_inverted_index.parameterization	59, 65
abstract_inverted_index.Karush-Kuhn-Tucker	26
abstract_inverted_index.constraint-learning	118
abstract_inverted_index.constraint-satisfying	128
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile